萌新求助模板Treap,80pts

rt,P3369过了

#include <bits/stdc++.h>
using namespace std;
const int INF=2147483647;
const int M=1100005;
inline void in (int &x){
    x=0;int f=1;char c=getchar();
    while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    x*=f;
}
inline void out (int x){
    char F[20];int tmp=x>0?x:-x,cnt=0;
    if (x<0) putchar('-');
    while (tmp){F[cnt++]=tmp%10+'0';tmp/=10;}
    while (cnt) putchar(F[--cnt]);puts ("");
}
int idx,root,n,m,op,x,last,ans;
struct Treap{
    int l,r;
    int val,dat;
    int siz,cnt;
}T[M];
inline int New (int v){
    T[++idx].val=v;
    T[idx].cnt=T[idx].siz=1;
    T[idx].dat=rand ();
    return idx;
}
inline void Update (int u){
    T[u].siz=T[T[u].l].siz+T[T[u].r].siz+T[u].cnt;
}
inline void Build (){
    New (-INF);New (INF);
    root=1;T[1].r=2;Update (root);
}
inline void zig (int &u){
    int p=T[u].l;T[u].l=T[p].r;T[p].r=u;u=p;
    Update (T[u].r);Update (u);
}
inline void zag (int &u){
    int p=T[u].r;T[u].r=T[p].l;T[p].l=u;u=p;
    Update (T[u].l);Update (u);
}
inline int GetRankByVal (int u,int v){
    if (!u) return 0;
    if (v==T[u].val) return T[T[u].l].siz+1;
    if (v>T[u].val) return GetRankByVal (T[u].r,v)+T[T[u].l].siz+T[u].cnt;
    return GetRankByVal (T[u].l,v);
}
inline int GetValByRank (int u,int k){
    if (!u) return INF;
    if (T[T[u].l].siz>=k) return GetValByRank (T[u].l,k);
    if (T[T[u].l].siz+T[u].cnt>=k) return T[u].val;
    return GetValByRank (T[u].r,k-T[T[u].l].siz-T[u].cnt);
}
inline void Insert (int &u,int v){
    if (!u){u=New (v);return ;}
    if (T[u].val==v){++T[u].cnt;Update (u);return ;}
    if (T[u].val>v){Insert (T[u].l,v);if (T[u].dat<T[T[u].l].dat) zig (u);}
    else{Insert (T[u].r,v);if (T[u].dat<T[T[u].r].dat) zag (u);}
    Update (u);
}
inline void Remove (int &u,int v){
    if (!u) return ;
    if (T[u].val==v){
        if (T[u].cnt>1){--T[u].cnt;Update (u);return ;}
        if (T[u].l||T[u].r){
            if (!T[u].r||T[T[u].r].dat<T[T[u].l].dat){zig (u);Remove (T[u].r,v);}
            else{zag (u);Remove (T[u].l,v);}
            Update (u);
        }
        else u=0;return ;
    }
    v<T[u].val?Remove (T[u].l,v):Remove (T[u].r,v);
    Update (u);
}
inline int GetPrev (int v){
    int ans=1,u=root;
    while (u){
        if (T[u].val==v){
            if (T[u].l){u=T[u].l;while (T[u].r) u=T[u].r;ans=u;}
            break;
        }
        if (T[u].val<v&&T[u].val>T[ans].val) ans=u;
        u=v<T[u].val?T[u].l:T[u].r;
    }
    return T[ans].val;
}
inline int GetNext (int v){
    int ans=2,u=root;
    while (u){
        if (T[u].val==v){
            if (T[u].r){u=T[u].r;while (T[u].l) u=T[u].l;ans=u;}
            break;
        }
        if (T[u].val>v&&T[u].val<T[ans].val) ans=u;
        u=v<T[u].val?T[u].l:T[u].r;
    }
    return T[ans].val;
}
signed main (){
    Build ();
    in (n);in (m);
    for (int i=1;i<=n;++i){
        in (x);Insert (root,x);
    }
    while (m--){
        in (op);in (x);x^=last;
        if (op==1) Insert (root,x);
        if (op==2) Remove (root,x);
        if (op==3){Insert (root,x);last=GetRankByVal (root,x)-1;Remove (root,x);ans^=last;}
        if (op==4){last=GetValByRank (root,x+1);ans^=last;}
        if (op==5){last=GetPrev (x);ans^=last;}
        if (op==6){last=GetNext (x);ans^=last;}
    }
    out (ans);
    return 0;
}