Hard Version的做法可以从Easy Version 用数据结构优化得到。
首先我们想一下，什么情况需要进行操作？显然是\(a_i!=b_i\)的时候，并且当\(a_i>b_i\)的时候将会无解。
那么当\(a_i<b_i\)的时候，应该怎么办呢，显然应该寻找左边和右边最近的\(j\),.满足\(a_j=b_i\)，
并且在\(j\)到\(i\)之间不存在一个点\(k\)，使\(a_k>b_i\)或者\(b_k<b_i\)，
那么对于Easy version，只要暴力循环检查就可以了.
对于Hard version，可以注意到最近的点可以用二分查找快速找到，而对于是否合法，可以用ST表快速得到区间最值来检查。
在这里仅展示Hard version的做法
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#include<bitset>
using namespace std;
int t;
int n;
int a[200005];
int b[200005];
int lg[200005];
int f[200005][22];
int g[200005][22];
void cal(){
for(int j=0;j<20;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
if(!j) f[i][j]=a[i],g[i][j]=b[i];
else{
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
}
}
}
}
void ini(){
lg[1]=0;
for(int i=2;i<=200000;++i)
lg[i]=lg[i>>1]+1;
}
int qmax(int l,int r){
int k=lg[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int qmin(int l,int r){
int k=lg[r-l+1];
return min(g[l][k],g[r-(1<<k)+1][k]);
}
void solve(){
for(int i=1;i<=n;++i)
if(a[i]>b[i]){
puts("NO");
return ;
}
cal();
vector<vector<int>>p(n+1);
for(int i=1;i<=n;++i)
p[i].push_back(0);
for(int i=1;i<=n;++i)
p[a[i]].push_back(i);
for(int i=1;i<=n;++i)
p[i].push_back(n+1);
int f=1;
for(int i=1;i<=n;++i){
int x=b[i];
if(b[i]==a[i]) continue;
int ff=0;
int r=upper_bound(p[x].begin(),p[x].end(),i)-p[x].begin();
int l=r-1;
r=p[x][r];
l=p[x][l];
if(l!=0){
if(qmax(l,i)==x&&qmin(l,i)==x)
ff=1;
}
if(r!=n+1){
if(qmax(i,r)==x&&qmin(i,r)==x)
ff=1;
}
if(!ff){
puts("NO");
return ;
}
}
puts("YES");
return ;
}
int main(){
ini();
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
solve();
}
return 0;
}