/*
排除掉所有不可能的情况，剩下的就是可行的
1.数的数量不相同
2.对任意一个区间进行排序，等价于可以交换任意逆序对，
那么从1到n扫描b数组，判断是否可以将a数组中等于b[i]的值所在的位置j交换到位置i，等价于判断区间a[i,j]是否存在<b[i]的数，判完后这个数不会再用到，所以改成无穷大
类似于一类偏序问题，可以建立线段树为维护动态区间最小值
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 300005
#define inf 0x3f3f3f3f
int a[maxn],b[maxn],ta[maxn],tb[maxn],n;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int Min[maxn<<
2];
void pushup(
int rt){
Min[rt]=min(Min[rt<<
1],Min[rt<<
1|
1]);
}
void build(
int l,
int r,
int rt){
if(l==
r){
Min[rt]=
a[l];
return;
}
int m=l+r>>
1;
build(lson);
build(rson);
pushup(rt);
}
void update(
int pos,
int val,
int l,
int r,
int rt){
if(l==
r){
Min[rt]=
val;
return;
}
int m=l+r>>
1;
if(pos<=
m)update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
}
int query(
int L,
int R,
int l,
int r,
int rt){
if(L<=l && R>=r)
return Min[rt];
int m=l+r>>
1,res=
0x3f3f3f3f;
if(L<=m)res=
min(res,query(L,R,lson));
if(R>m)res=
min(res,query(L,R,rson));
return res;
}
queue<
int>
q[maxn];
int main(){
int t;
cin>>
t;
while(t--
){
cin>>
n;
for(
int i=
1;i<=n;i++
){
cin>>a[i],ta[i]=
a[i];
while(q[a[i]].size())q[a[i]].pop();
}
for(
int i=
1;i<=n;i++)cin>>b[i],tb[i]=
b[i];
sort(ta+
1,ta+
1+n);sort(tb,tb+
1+
n);
int flag=
0;
for(
int i=
1;i<=n;i++
)
if(ta[i]!=tb[i])flag=
1;
if(!
flag){
build(1,n,
1);
for(
int i=
1;i<=n;i++
)
q[a[i]].push(i);
for(
int i=
1;i<=n;i++
){
int pos=
q[b[i]].front();
q[b[i]].pop();
int tmp=query(
1,pos,
1,n,
1);
update(pos,inf,1,n,
1);
if(tmp<b[i])flag=
1;
}
}
if(flag)puts(
"NO");
else puts(
"YES");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11115015.html
