Description

在七山七海之外的一个小村庄，白雪公主与N个矮人住在一起，所有时间都花在吃和玩League of Legend游戏。白雪公主决心终结这样的生活，所以为他们举办了体育课。 在每节课开始时，矮人必须按他们的身高站队。假定矮人们有高度1，2，...，N（每个人高度互不相同）。然而，由于不健康的生活方式，矮人的智力有所恶化，所以他们没有能力依照自己的高度排序。

因此，白雪公主发出以下形式命令帮助他们：

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）。

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 
      
       #include 
       
        #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
        
         
          
           >1,c1=type?0:Inf,c2=c1;    if (ll<=mid) c1=Query(lson,l,mid,ll,rr,type);    if (mid
           
            >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"); } }}