题意：给两个数字序列a,b，在给出m次区间，每次区间操作可以对L[i]~R[i]间的数字进行任意排列，问序列a能否在m次操作后变为序列b.
思路：贪心思想，每次操作都使a[i]尽可能的靠近它的期望位置，所以对每个操作区间按照它的期望位置排序，结果和b序列一样那就YES。O(n^2)可以处理出每个a[i]的期望位置。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #define LL long long #define eps 1e-8 #define maxn 150 #define mod 110119 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std; struct node{ int num; int to; }a[1005]; int b[1005]; int L[1005],R[1005]; bool vis[1005]; bool cmp(struct node x,struct node y){ return x.to<y.to; } int main(){ // IN; int t; int n,m; cin>>t; while(t--){ memset(vis,false,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i].num); } for(int i=1;i<=n;i++){ scanf("%d",&b[i]); } for(int i=1;i<=m;i++){ scanf("%d%d",&L[i],&R[i]); } int sign1=0,sign2=0; for(int i=1;i<=n;i++){ sign1=0; for(int j=1;j<=n;j++){ if(a[i].num==b[j] && !vis[j]){ a[i].to=j; vis[j]=true; sign1=1; break; } } if(sign1==0) sign2=1; } if(sign2==1){ printf("No\n"); continue; } for(int i=1;i<=m;i++){ sort(a+L[i],a+R[i]+1,cmp); } sign2=0; for(int i=1;i<=n;i++){ if(a[i].num!=b[i]){ sign2=1; break; } } if(sign2==1){ printf("No\n"); }else{ printf("Yes\n"); } } return 0; }
