题目大意
有两个长度为(n)的序列(a_1,...,a_n)，(b_1,...,b_n)（(a,bleq nleq 3 imes 10^5) ）。一次操作是选取 ([l,r]) ，将 (a_l,...,a_r) 排序。问能否通过若干次操作把 (a_1,...,a_n) 变得和 (b_1,...,b_n) 一样。
题解
这个人讲得很清楚
首先，如果(a,b)中每个数的出现次数不一样，那么一定不能。
其余的部分的问题在于能不能通过交换(a)中一些数的位置使(a)变得和(b)一样。
设(a)中两个位置(i,j)的数在(b)中的位置为(i',j')。
当(i<j)且(i'>j')时，要想使(a,b)相同必须交换(i,j)的位置，一定存在一次操作使([i,j]in[l,r])。
当(a_i<a_j)且(i'>j')时，如果存在一次操作([i,j]in[l,r])，那么(a_i)就会被换到(a_j)左边，而且没法再换回来了，所以此时对于任意一次操作都没有([min(i,j),max(i,j)]in[l,r])。
所以当存在(a_i<a_j)且(i<j)且(i'>j')时，一定没有合法解。
想要判断这部分，可以从左往右扫序列(b)，对于(b_i)，设(b_i)在(a)中目前第一次出现的位置为(p(i))，若(min{a_j|jin[1,p(i)]}<b_i)那么就没有合法解；反之，将(a_{p(i)})改为(+inf)，继续判断剩下的。
代码
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define LL long long
#define maxn 300007
#define ls (u<<1)
#define rs (u<<1|1)
#define mi (l+r>>1)
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x==0){putchar('0'),putchar(' ');return;}
int f=0;char ch[20];
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar(' ');
return;
}
int t,n,a[maxn],b[maxn],tr[maxn<<2],ta[maxn],tb[maxn],fir[maxn],nxt[maxn];
void pu(int u){tr[u]=min(tr[ls],tr[rs]);}
void add(int u,int l,int r,int x,int k)
{
if(x<=l&&r<=x){tr[u]=k;return;}
if(x<=mi)add(ls,l,mi,x,k);
else add(rs,mi+1,r,x,k);
pu(u);return;
}
int ask(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return tr[u];
int res=n+1;
if(x<=mi)res=ask(ls,l,mi,x,y);
if(y>mi)res=min(res,ask(rs,mi+1,r,x,y));
return res;
}
void build(int u,int l,int r)
{
if(l==r){tr[u]=a[l];return;}
build(ls,l,mi),build(rs,mi+1,r),pu(u);return;
}
int main()
{
t=read();
while(t--)
{
n=read();int ans=1;
rep(i,1,n)ta[i]=a[i]=read(),fir[i]=-1;
rep(i,1,n)tb[i]=b[i]=read();
sort(ta+1,ta+n+1),sort(tb+1,tb+n+1);
rep(i,1,n)if(ta[i]!=tb[i]){ans=0;break;}
if(!ans){puts("NO");continue;}
build(1,1,n);
dwn(i,n,1){nxt[i]=fir[a[i]],fir[a[i]]=i;}
rep(i,1,n)
{
int pos=fir[b[i]],mn=ask(1,1,n,1,pos);fir[b[i]]=nxt[pos];
if(mn<b[i]){ans=0;break;}
add(1,1,n,pos,n+1);
}
if(!ans)puts("NO");
else puts("YES");
}
return 0;
}
WAWAWAWA
1.将(b)分成很多段，每一段连续且不下降且尽可能长。若(b)一段中的每个数的个数和(a)对应这一段位置的每个数的个数不同，那么NO，否则YES。
2.最小的数无法往右走但往左走多远都行，…，最大的数无法往左走但往右走多远都行。计算(a)中每个数最多往右走几个、最多往左走几个，如果这个数在(a)中的位置和它在(b)中的位置的差距大于这个范围，就NO，否则YES。
3.正解，但没有判(a，b)整体上是不是所有数的个数一样。
4.正解，但是没有反着求“fir”“nxt”。