$solution:$
可以发现对区间 $[l,r]$ 排序可以每次只排序 $2$ 个然后冒泡，所以用 $2$ 个和用多个是等价的。
假设现在 $b_1$ 到 $b_{i-1}$ 已经还原，现在考虑 $b_i$ 。
可以发现若存在 $a_j$ 可以与 $b_i$ 配对的条件是 $min{a_1,a_{i+1},,a_j}=a_j$ 时才可以配对，并且 $a$ 的其余数相对位置保持不变，所以只要将配对的 $a$ 赋为 $INF$ 即可。
即只要维护一个单点修改，区间最值的线段树即可。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<vector> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=300001; int a[MAXN],b[MAXN],INF=INT_MAX; vector<int> ve[MAXN]; struct Segment{ int minn[MAXN<<2]; void clear(){memset(minn,127/3,sizeof(minn));} void cle(int k,int l,int r){ if(l==r){minn[k]=INF;return;} int mid=l+r>>1; cle(k<<1,l,mid),cle(k<<1|1,mid+1,r); minn[k]=min(minn[k<<1],minn[k<<1|1]); } void build(int k,int l,int r){ if(l==r){minn[k]=a[l];return;} int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); minn[k]=min(minn[k<<1],minn[k<<1|1]); return; } int Query(int k,int l,int r,int x,int y){ if(x<=l&&r<=y) return minn[k]; int mid=l+r>>1,res=INT_MAX; if(x<=mid) res=min(res,Query(k<<1,l,mid,x,y)); if(mid<y) res=min(res,Query(k<<1|1,mid+1,r,x,y)); return res; } void update(int k,int l,int r,int x,int y,int w){ if(x<=l&&r<=y){minn[k]=w;return;} int mid=l+r>>1,res=INT_MAX; if(x<=mid) update(k<<1,l,mid,x,y,w); if(mid<y) update(k<<1|1,mid+1,r,x,y,w); minn[k]=min(minn[k<<1],minn[k<<1|1]); return; } }segment; int T,n,M[MAXN]; int main(){ T=read(); segment.clear(); while(T--){ n=read(); for(int i=1;i<=n;i++) a[i]=read(),ve[a[i]].push_back(i); for(int i=1;i<=n;i++) b[i]=read(); bool f=1;segment.build(1,1,n); for(int i=1;i<=n;i++){ M[b[i]]++; if(ve[b[i]].size()<M[b[i]]){f=0;printf("NO ");break;} if(segment.Query(1,1,n,1,ve[b[i]][M[b[i]]-1])!=b[i]){f=0;printf("NO ");break;} segment.update(1,1,n,ve[b[i]][M[b[i]]-1],ve[b[i]][M[b[i]]-1],INF); }if(f) printf("YES "); for(int i=1;i<=n;i++) M[b[i]]=0,ve[a[i]].clear(); segment.cle(1,1,n); }return 0; }