CAP5_Monday

A Set to Max (Easy Version)

给定数组 a 和 b，可以执行以下操作任意次 :

让 $a_l\sim a_r$ 中的所有所有元素变成 $a_i$ $(l\le i\le r)$， 其中 $1\le l\le r\le n$

显然, 必须满足任意 $a_i\le b_i$ , 否则无解。

从 1 到 n 遍历 a[i],
如果 a[i] = b[i], continue;
否则, a[i] < b[i]
必须从 [1, n] 中寻找 mx = b[i], 设 mx_pos = j > i
则 b[i, mx_pos] = b[i] 才能更换
也就以 b 为节点扩展 ???

1 2 3 2 4

1 3 3 2 4

遍历 b 似乎更优秀,

1 = 1 ，下一个

3 > 2,

寻找 a[j] = 3 了 & 途中没出现更大的数 & 途中 $b_j$ 全部等于 $b_i$

2 = 2

4 = 4

YES

---

3 4 2 2 4

3 4 3 4 4

3 = 3

4 = 4

3 > 2

下一个 下一个 $b_i\ne 3$

NO

---

3 2 1 1 1

3 3 3 2 2

3 = 3

3 > 2

下一个 $b_j=3$ & $a_j<3$

还可以向左边找

我们双指针预处理所有的 $b_i$ 相同块

【3 2 1】【1 1】

【3 3 3】【2 2】

块中的 $a_i$ 最大值 = b 即可

还是错了，应该从值最小的块操作，以 【2 2】为例，查询到所有的 2 , 统一修改即可

3 2 2 2 2

3 3 3 2 2

---

1 1

1 2

NO

---

1 1 2

2 1 2

不能跨越已经修改的元素

NO

---

综上，按值大小预处理离出来每个相同块加入 vector , 从小到大遍历，$st$ 维护一个块是否已经铆定，也就是是否还接受修改；对于每个查询修改，先遍历 [l, r] 看看有没有对应元素，有就直接修改，没有的话先左在右，实在不行在 return false

---

猜想确实是对的，但是 $O(n^2)$ 的时间复杂度不足以通过 $Hard$ 版本

B Set To Max (Hard Version)

这是 easy 版本的 ac code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1100], b[1100];
vector<pair<int, int> > seg[1100];
bool st[1100];
void solve(){cin >> n;for(int i = 1; i <= n; i ++){st[i] = false;seg[i].clear();}for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n; i ++){cin >> b[i];}for(int i = 1; i <= n; i ++){if(a[i] > b[i]){cout << "NO\n";return ;}}for(int i = 1; i <= n; i ++){int j = i;while(j <= n && b[j] == b[i]) j ++;j --;seg[b[i]].push_back({i, j});i = j;}// for(int i = 1; i <= n; i ++){//     if(seg[i].size()==0) continue;//     cout<<i<<": \n";//     for(auto [l, r] : seg[i]){//         cout<<l<<' '<<r<<'\n';//     }// }for(int v = 1; v <= n; v ++){if(seg[v].size() == 0) continue;for(auto [l, r] : seg[v]){int val = b[l];bool fg = false;for(int k = l; k <= r; k ++){if(a[k] == val) fg = true;}if(fg){for(int k = l; k <= r; k ++){st[k] = true; // 不再修改//    cout<<"k: "<<k<<'\n';}continue;}else{for(int i = l - 1; i >= 1; i --){if(st[i] == true || a[i] > val){break;}if(a[i] == val){fg = true;for(int u = l; u <= r; u ++) st[u] = true;break;}}for(int i = r + 1; !fg && i <= n; i ++){if(st[i] == true || a[i] > val){break;}if(a[i] == val){fg = true;for(int u = l; u <= r; u ++) st[u] = true;break;}}if(fg == false){cout << "NO\n";return ;}}}}cout << "YES\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
// 1
// 25// 7 2 2 6  8  6 3  1  11 7  13 3   9 5  1  17 3  7  11 4  2  2  9  8  2
// 7 8 8 8 11 13 13 13 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 2// st[25] = true
// st[1] = true

复杂度较为集中的区域是查询以及区间修改为 true

区间查询的是区间 mx, 这时可以维护一个线段树，线段树里面维护 st 数组，每次修改为 true 就是区间修改 1, 然后查找对应的 val 值的过程，查 st 用二分，查 mx 也用二分

查 st 的二分, 就是确定 mx 二分的边界, 看看 mx 从 [l, r] 往左查和往右查能不能查到 mx

但这题绝对不会这么复杂，维护区间修改 + 查询区间和 + 求区间 mx 的线段树略显复杂（不难但我不会），但是是一种可行的做法

---

从小到大枚举块，每个块覆盖的 $a_i$ ,

对于第一个块，可以选择 从 [1, n] 里面查找 val

维护区间查询 mx, map 映射快速查询 val 的位置，首先自己查自己的 [l, r] 区间加起来是 O(n) 的可以接受；每个点只会被修改为 true 一次，同样是 $O(n)$ 的。

只用看看 [lpos, l-1] 和 [r+1, rpos] 之间有没有 st = true 的即可

这样还是很好写的，维护一个 set 存 st=true 的位置即可，在 st 里面二分看看最近的非法位置 ??

只需要 STl 就能实现，不需要额外的手写的复杂数据结构

---

我发现自己的代码忽略了一个致命问题，就是

只用看看 [lpos, l-1] 和 [r+1, rpos] 之间有没有 st = true 的即可

这句话部分对了，还要查看这里面有没有比 val 大的，还要维护操蛋的数据结构

已经2024年4月15日22:05:20了，明天直接看题解补题把

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1100], b[1100];
vector<pair<int, int> > seg[1100];
// bool st[1100];
set<int> pos[200010]; // 值 i 的 pos
void solve(){set<int> st = set<int> (); // 维护 truecin >> n;for(int i = 1; i <= n; i ++){//	st[i] = false;seg[i].clear();pos[i].clear();}for(int i = 1; i <= n; i ++){cin >> a[i];pos[a[i]].insert(i);}for(int i = 1; i <= n; i ++){cin >> b[i];}for(int i = 1; i <= n; i ++){if(a[i] > b[i]){cout << "NO\n";return ;}}for(int i = 1; i <= n; i ++){int j = i;while(j <= n && b[j] == b[i]) j ++;j --;seg[b[i]].push_back({i, j});i = j;}// for(int i = 1; i <= n; i ++){// 	if(seg[i].size()==0) continue;// 	cout<<i<<": \n";// 	for(auto [l, r] : seg[i]){// 		cout<<l<<' '<<r<<'\n';// 	}// }for(int v = 1; v <= n; v ++){if(seg[v].size() == 0) continue;for(auto [l, r] : seg[v]){int val = b[l];bool fg = false;for(int k = l; k <= r; k ++){ // 内部查询暴力查if(a[k] == val) fg = true;}if(fg){for(int k = l; k <= r; k ++){st.insert(k);pos[a[k]].erase(k);pos[val].insert(k);//	st[k] = true; // 不再修改//	cout<<"k: "<<k<<'\n';}continue;}else{// 从左边用 set::pos 快速查询if(pos[val].size() == 0){cout << "NO\n";return ;}if(*pos[val].begin() < l){auto it = pos[val].lower_bound(l);it = prev(it); // =val 最接近 l 的元素//			cout << "*it: " << (*it) << '\n';//			cout << *st.lower_bound(*it) << '\n';if(st.size()==0 || *st.lower_bound(*it) < (*it)){fg = true;for(int k = l; k <= r; k ++){st.insert(k);pos[a[k]].erase(k);pos[val].insert(k);//	st[k] = true; // 不再修改//	cout<<"k: "<<k<<'\n';}}}  if(fg == false){auto it = pos[val].lower_bound(r);if(it != pos[val].end()){if(st.size()==0 || *st.lower_bound(r) > *it){fg = true;for(int k = l; k <= r; k ++){st.insert(k);pos[a[k]].erase(k);pos[val].insert(k);//	st[k] = true; // 不再修改//	cout<<"k: "<<k<<'\n';}}}}if(fg == false){cout << "NO\n";return ;}}}}cout << "YES\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}
// 1
// 25// 7 2 2 6  8  6 3  1  11 7  13 3   9 5  1  17 3  7  11 4  2  2  9  8  2
// 7 8 8 8 11 13 13 13 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 2// st[25] = true
// st[1] = true