Description
在七山七海之外的一个小村庄,白雪公主与N个矮人住在一起,所有时间都花在吃和玩League of Legend游戏。白雪公主决心终结这样的生活,所以为他们举办了体育课。 在每节课开始时,矮人必须按他们的身高站队。假定矮人们有高度1,2,...,N(每个人高度互不相同)。然而,由于不健康的生活方式,矮人的智力有所恶化,所以他们没有能力依照自己的高度排序。
因此,白雪公主发出以下形式命令帮助他们:
1 X Y:X和Y位置的矮人互换位置。
2 A B:询问高度为A,A+1,..., B的矮人(不一定是按照这个顺序)是否已形成了当前队列的连续子序列。
帮助矮人按照白雪公主的指示行动,并回答她的问题。
因此,白雪公主发出以下形式命令帮助他们:
1 X Y:X和Y位置的矮人互换位置。
2 A B:询问高度为A,A+1,..., B的矮人(不一定是按照这个顺序)是否已形成了当前队列的连续子序列。
帮助矮人按照白雪公主的指示行动,并回答她的问题。
Input
输入的第一行包含两个正整数N和M,分别表示矮人的数量和白雪公主的命令数,2≤N≤200,000,2≤M≤200,000。
第二行包含N个用空格隔开的从1到N的正整数,每个数只出现一次,代表矮人的初始排列。
接下来的M行包含白雪公主的命令,形式为“1 X Y”(1≤X,Y≤N,X≠Y)或“2 A B”(1≤A≤B≤N)。
第二行包含N个用空格隔开的从1到N的正整数,每个数只出现一次,代表矮人的初始排列。
接下来的M行包含白雪公主的命令,形式为“1 X Y”(1≤X,Y≤N,X≠Y)或“2 A B”(1≤A≤B≤N)。
Output
对于每个命令2输出“YES”或“NO”。
Sample Input
输入1:
5 3
2 4 1 3 5
2 2 5
1 3 1
2 2 5
输入2:
7 7
4 7 3 5 1 2 6
2 1 7
1 3 7
2 4 6
2 4 7
2 1 4
1 1 4
2 1 4
Sample Output
输出1:
NO
YES
输出2:
YES
NO
YES
NO
YES
Data Constraint
50%的数据:类型2询问中A,B满足B-A≤50
分析
我考场上居然有会做的题?!
权值线段树随便搞,只要这段权值中的最大rk和最小rk相减等于最大权值-最小权值即在连续一段
#include <iostream> #include <cstdio> #define lson (x<<1) #define rson ((x<<1)+1) using namespace std; const int N=2e5+10; const int Inf=2147483647; struct Node {int mx,mn; }t[4*N]; int n,m,a[N],rk[N],rev[N];void Update(int x) {t[x].mx=max(t[lson].mx,t[rson].mx);t[x].mn=min(t[lson].mn,t[rson].mn); }void Build(int x,int l,int r) {if (l==r) {t[x].mx=t[x].mn=rk[l];return;}int mid=l+r>>1;Build(lson,l,mid);Build(rson,mid+1,r);Update(x); }int Query(int x,int l,int r,int ll,int rr,int type) {if (rr<l||r<ll|r<l) return type?0:Inf;if (ll<=l&&r<=rr) return type?t[x].mx:t[x].mn;int mid=l+r>>1,c1=type?0:Inf,c2=c1;if (ll<=mid) c1=Query(lson,l,mid,ll,rr,type);if (mid<rr) c2=Query(rson,mid+1,r,ll,rr,type);return type?max(c1,c2):min(c1,c2); }void Change(int x,int l,int r,int k,int z) {if (l==r&&r==k) {t[x].mx=t[x].mn=z;return;}int mid=l+r>>1;if (k<=mid) Change(lson,l,mid,k,z);else Change(rson,mid+1,r,k,z);Update(x); }int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),rk[a[i]]=i;for (int i=1;i<=4*n;i++) t[i].mx=0,t[i].mn=Inf;Build(1,1,n);for (int i=1;i<=m;i++) {int ord,l,r;scanf("%d%d%d",&ord,&l,&r);if (ord==1) {l=a[l];r=a[r];int A=Query(1,1,n,l,l,1),B=Query(1,1,n,r,r,1);Change(1,1,n,l,B);Change(1,1,n,r,A);swap(a[rk[l]],a[rk[r]]);swap(rk[l],rk[r]);}else {int mx=Query(1,1,n,l,r,1),mn=Query(1,1,n,l,r,0);if (mx-mn==r-l) printf("YES\n");else printf("NO\n");}} }