Codeforces 1187 D. Subarray Sorting —— 线段树，贪心

本文主要是介绍Codeforces 1187 D. Subarray Sorting —— 线段树，贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有两个数组，并且你每次可以做一个操作：选择一个区间，并且排序。
问你对上面这个数组做一些操作之后是否能得到下面这个数组。

题解：

那么如果每次选的区间大小为2，那么就像是一个冒泡排序了，将一个大的值依次向后传并且保持其他的值顺序不变。
那么我们只需要从后往前枚举一遍b数组，然后查看a数组对应的bi的值的最后一个位置到n的最大值是否有一个数大于他。如果有就不行，因为他没有办法交换到后面去。如果行那就将这个值去掉，因为它已经排好了。我用线段树维护最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int a[N],b[N],mx[N*4];
queue<int>Q[N];
void update(int l,int r,int root,int p,int v){if(l==r){mx[root]=v;return ;}int mid=l+r>>1;if(mid>=p)update(l,mid,root<<1,p,v);elseupdate(mid+1,r,root<<1|1,p,v);mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
int query(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return mx[root];int mid=l+r>>1,ans=0;if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr)ans=max(ans,query(mid+1,r,root<<1|1,ql,qr));return ans;
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),update(1,n,1,i,a[i]);for(int i=n;i;i--)Q[a[i]].push(i);for(int i=1;i<=n;i++)scanf("%d",&b[i]);int f=0;for(int i=n;i;i--){if(Q[b[i]].empty()){f=1;break;}int p=Q[b[i]].front();Q[b[i]].pop();if(query(1,n,1,p,n)>b[i]){f=1;break;}update(1,n,1,p,0);}for(int i=1;i<=n;i++)while(!Q[i].empty())Q[i].pop();if(f)printf("NO\n");else printf("YES\n");}return 0;
}

这篇关于Codeforces 1187 D. Subarray Sorting —— 线段树，贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---