首先区间排序就相当于交换相邻两个数，前面的数要大于后面的数才能交换。
然后就不会了……
我们考虑 $b_1$ 到 $b_{i-1}$ 都已经归位了，现在要把 $b_i$ 归位。
找到其在 $a$ 中下一次出现的位置（设为 $p$）。发现只有当 $a_p$ 是 $a_i$ 到 $a_p$ 的最小值时，才能归到。
具体代码实现时不会改变 $a$ 的位置，那怎么判断最小值呢？发现已经归位的数对最小值没有贡献，可以归位后就变成 INF。然后询问 $1$ 到 $p$ 的最小值即可。
时间复杂度 $O(n\log n)$。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=300030; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<\'0\' || ch>\'9\') f|=ch==\'-\',ch=getchar(); while(ch>=\'0\' && ch<=\'9\') x=x*10+ch-\'0\',ch=getchar(); return f?-x:x; } int t,n,a[maxn],b[maxn],ta[maxn],tb[maxn],mn[maxn*4],len[maxn]; vector<int> at[maxn]; inline void pushup(int o){ mn[o]=min(mn[o<<1],mn[o<<1|1]); } void build(int o,int l,int r){ if(l==r) return void(mn[o]=a[l]); int mid=(l+r)>>1; build(lson);build(rson); pushup(o); } void update(int o,int l,int r,int p,int v){ if(l==r) return void(mn[o]=v); int mid=(l+r)>>1; if(mid>=p) update(lson,p,v); else update(rson,p,v); pushup(o); } int query(int o,int l,int r,int ql,int qr){ if(l>=ql && r<=qr) return mn[o]; int mid=(l+r)>>1,ans=2e9; if(mid>=ql) ans=min(ans,query(lson,ql,qr)); if(mid<qr) ans=min(ans,query(rson,ql,qr)); return ans; } int main(){ t=read(); while(t--){ bool flag=true; n=read(); FOR(i,1,n) ta[i]=a[i]=read(),at[a[i]].push_back(i); FOR(i,1,n) tb[i]=b[i]=read(); sort(ta+1,ta+n+1);sort(tb+1,tb+n+1); FOR(i,1,n) if(ta[i]!=tb[i]){puts("NO");flag=false;break;} if(!flag){ FOR(i,1,n) at[i].clear(),len[i]=0; continue; } build(1,1,n); FOR(i,1,n){ int p=at[b[i]][len[b[i]]++]; if(query(1,1,n,1,p)!=b[i]){puts("NO");flag=false;break;} update(1,1,n,p,2e9); } if(flag) puts("YES"); FOR(i,1,n) at[i].clear(),len[i]=0; } }