Treap32分求助

/*  Name:P6136
    Copyright:[Xcoi]
    Author:xbb2
    Date:2022.8.22
    Description:*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,lst;
struct treap{
    int lc[N],rc[N],sz=0,rt=0;
    int val[N],rnd[N],siz[N],w[N];
    inline void pushup(int x){siz[x]=siz[lc[x]]+siz[rc[x]]+w[x];}
    inline void lrotate(int &root){
        int tmp=rc[root];
        rc[root]=lc[tmp],lc[tmp]=root;
        siz[tmp]=siz[root];
        pushup(root);
        root=tmp;
    }
    inline void rrotate(int &root){
        int tmp=lc[root];
        lc[root]=rc[tmp],rc[tmp]=root;
        siz[tmp]=siz[root];
        pushup(root);
        root=tmp;
    }
    inline void insert(int &root,int x){
        if(!root){
            sz++,root=sz;
            siz[root]=w[root]=1;
            val[root]=x,rnd[root]=rand();
            return ;
        }
        siz[root]++;
        if(val[root]==x)w[root]++;
        else if(val[root]<x){
            insert(rc[root],x);
            if(rnd[rc[root]]<rnd[root])lrotate(root);
        }
        else{
            insert(lc[root],x);
            if(rnd[lc[root]]<rnd[root])rrotate(root);
        }
    }
    inline bool del(int &root,int x){
        if(!root)return false;
        if(val[root]==x){
            if(w[root]>1){w[root]--,siz[root]--;return true;};
            if(!lc[root]||!rc[root]){
                root=lc[root]+rc[root];
                return true;
            }
            else if(rnd[lc[root]]<rnd[rc[root]]){
                rrotate(root);return del(root,x);
            }
            else{
                lrotate(root);return del(root,x);
            }
        }
        else if(val[root]<x){
            bool flag=del(rc[root],x);
            if(flag)siz[root]--;
            return flag;
        }
        else{
            bool flag=del(lc[root],x);
            if(flag)siz[root]--;
            return flag;
        }
    }
    inline int queryrnk(int root,int x){
        if(!root)return 0;
        if(val[root]==x)return siz[lc[root]]+1;
        else if(x>siz[lc[root]]+w[root])
            return siz[lc[root]]+w[root]+queryrnk(rc[root],x);
        else return queryrnk(lc[root],x);
    }
    inline int querynum(int root,int x){
        if(!root)return 0;
        if(x<=siz[lc[root]])return querynum(lc[root],x);
        else if(x>siz[lc[root]]+w[root])
            return querynum(rc[root],x-siz[lc[root]]-w[root]);
        else return val[root];
    }
    int ans=0;
    inline void querypre(int root,int x){
        if(!root)return ;
        if(val[root]<x)ans=root,querypre(rc[root],x);
        else querypre(lc[root],x);
    }
    inline void querysub(int root,int x){
        if(!root)return ;
        if(val[root]>x)ans=root,querysub(lc[root],x);
        else querysub(rc[root],x);
    }
}T;
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    srand(time(NULL));
    cin>>n>>m;int ans=0;
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        T.insert(T.rt,x);
    }
    for(int i=1;i<=m;i++){
        int opt,x;
        scanf("%d%d",&opt,&x),x^=lst;
        if(opt==1) T.insert(T.rt,x); 
        else if(opt==2) T.del(T.rt,x); 
        else if(opt==3) lst=T.queryrnk(T.rt,x),ans^=lst;
        else if(opt==4) lst=T.querynum(T.rt,x),ans^=lst;
        else if(opt==5) T.querypre(T.rt,x),lst=T.ans,ans^=lst;
        else if(opt==6) T.querysub(T.rt,x),lst=T.ans,ans^=lst;
//      printf("%d %d\n",opt,x);
    }
    printf("%d",ans);
    return 0;
}