D.?Set To Max
題目：
?
Easy
思路：
簡單題
由于題目的數據給的很小，所以我們可以用 n2 的復雜度過，那我們來觀察一下我們應該怎么操作
顯然，如果 a[i] > b[i] 時是無法構造的，同時 a[i] = b[i] 時就不用管了，所以我們直接看 a[i] < b[i]
既然我們要使得這一點可以變成 b[i]，那么我們向左右兩邊尋找一下即可，顯然第一個 a[j] = b[i] 的點 j 是最優的，因為如果?j 不行，那么之后的點肯定也不符合，所以我們只要向左和向右找是否存在 a[j] = b[i] 的點 j 即可
但是沒有什么特殊條件嗎？
顯然肯定有的，如果遇到了 a[j] > b[i]，那我們就不能繼續找了，否則到時候會把 a[i] 變成比 b[i] 還大的 a[j]，所以肯定不行
那么還有嗎？
當然，我們再想想，如果我們向左找的時候遇到一個點有 b[j] < b[i] 會發生什么，如果我們要替換，無論此時 a[j] = b[j] 還是 a[j] < b[j] ，既然我們包括了這個區間，那么最后 a[j] 一定會變成 比b[j] 更大的 b[i]，因此我們遇到 b[j] < b[i] 時也要停止
為什么這樣找是可行的呢？
因為這一題我們可以按照任意順序執行，所以我們找到對應的點后只需要從小到大操作即可，雖然這一題并沒有讓我們輸出操作
代碼：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"void solve()
{int n;cin >> n;vector<int> a(n), b(n);set<int> ahas;for (int i = 0; i < n; i++){cin >> a[i];ahas.insert(a[i]);}int flag = 0;for (int i = 0; i < n; i++){cin >> b[i];if (a[i] > b[i] || !ahas.count(b[i])){flag = 1;}}if (flag){no;return;}for (int i = 0; i < n; i++){if (a[i] == b[i])continue;int can = 0;for (int j = i- 1; j >= 0; j--){if (a[j] > b[i] || b[j] < b[i])break;if (a[j] == b[i]){can = 1;break;}}for (int j = i + 1; j < n; j++){if (a[j] > b[i] || (a[j] == b[j] && b[j] < b[i]))break;if (a[j] == b[i]){can = 1;break;}}if (!can){no;return;}}yes;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}Hard
思路：
考優化，二分 + ST表
由于困難版 n 變大了，因此我們不能左右依次枚舉 j 了，那我們怎么找呢？
我們其實可以將 a[i] 的位置 i 存下來，那我們查找的時候只需要使用二分去 pos[b[i]] 中尋找 第一個大于 i 的位置 j 和 最后一個小于 i 的位置 j
找是找到了，但是那些判斷怎么寫？
我們觀察easy我們找到的條件，第一個是不能存在 b[i] >?b[j] 第二個不能存在 a[j] > b[i]，所以我們需要快速找到 j ~ i 這個區間的最大值和最小值，只要 MAX 和 MIN 都滿足條件，那么其他點肯定也是滿足條件的，對于 區間最大值/最小值 (RMQ) 問題，我們可以使用 ST 表 或者 樹狀數組，這里使用 ST 表實現
至此優化問題就解決了
代碼：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int MAXN = 2e5 + 10;int lg[MAXN];
int n;
int stMX[MAXN][20], stMI[MAXN][20];
void InitLog()
{lg[1] = 0;for (int i = 2; i <= 2e5; i++)lg[i] = lg[i >> 1] + 1;
}void InitST()
{for (int j = 1; j <= lg[n]; j++){for (int i = 1; i + (1LL << j) - 1 <= n; i++){stMX[i][j] = max(stMX[i][j - 1], stMX[i + (1LL << (j - 1))][j - 1]);stMI[i][j] = min(stMI[i][j - 1], stMI[i + (1LL << (j - 1))][j - 1]);}}
}int getMax(int l,int r)
{int len = lg[r - l + 1];return max(stMX[l][len], stMX[r - (1LL << len) + 1][len]);
}int getMin(int l, int r)
{int len = lg[r - l + 1];return min(stMI[l][len], stMI[r - (1LL << len) + 1][len]);
}int erfengetSmall(int x,vector<int>& pos)
{int l = 0, r = pos.size() - 1;int res = -1;while (l <= r){int mid = l + r >> 1;if (pos[mid] < x){res = mid;l = mid + 1;}else{r = mid - 1;}}return res;
}void solve()
{cin >> n;vector<int> a(n+1), b(n+1);vector<vector<int>> pos(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];stMX[i][0] = a[i];pos[a[i]].push_back(i);}for (int i = 1; i <= n; i++){cin >> b[i];stMI[i][0] = b[i];}InitST();for (int i = 1; i <= n; i++){int flag = 0;if (a[i] == b[i])continue;if (a[i] > b[i]){no;return;}if (!pos[b[i]].empty()){auto it = lower_bound(pos[b[i]].begin(), pos[b[i]].end(), i);if (it != pos[b[i]].end()){int r = *it;if (getMax(i, r) <= b[i] && getMin(i, r) >= b[i]){flag = 1;}}int L = erfengetSmall(i, pos[b[i]]);if (L >= 0){int l = pos[b[i]][L];if (getMax(l, i) <= b[i] && getMin(l, i) >= b[i]){flag = 1;}}}if (!flag){no;return;}}yes;
}signed main()
{InitLog();cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}
)
