Treap 30pts 求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
inline long long read(){
    long long num=0;int z=1;char c=getchar();
    if(c=='-') z=-1;
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') z=-1,c=getchar();
    while(c>='0'&&c<='9') num=(num<<1)+(num<<3)+(c^48),c=getchar();
    return z*num;
}
const int Maxn=1e6+1e5+5;
int n,m;
class Tr{
    public:
        struct Treap{
            int l,r;
            int val,dat;
            int cnt,size;
        }a[Maxn];
        int tot,root;
        int New(int val){
            a[++tot].val=val;
            a[tot].dat=rand();
            a[tot].cnt=a[tot].size=1;
            return tot;
        }
        il void update(int p){
            a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;
            return ;
        }
        il void build(){
            New(-INF),New(INF);
            root=1,a[1].r=2;
            update(root);
        }
        il int GetRankByVal(int p,int val){
            if(!p) return 0;
            if(val==a[p].val) return a[a[p].l].size+1;
            if(val<a[p].val) return GetRankByVal(a[p].l,val);
            return GetRankByVal(a[p].r,val)+a[a[p].l].size+a[p].cnt;
        }
        il int GetValByRank(int p,int rank){
            if(!p) return 0;
            if(a[a[p].l].size>=rank) return GetValByRank(a[p].l,rank);
            if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
            return GetValByRank(a[p].r,rank-a[a[p].l].size-a[p].cnt);
        }
        il void zig(int &p){
            int q=a[p].l;
            a[p].l=a[q].r,a[q].r=p,p=q;
            update(a[p].r),update(p);
            return ;
        }
        il void zag(int &p){
            int q=a[p].r;
            a[p].r=a[q].l,a[q].l=p,p=q;
            update(a[p].l),update(p);
        }
        il void Insert(int &p,int val){
            if(!p){
                p=New(val);
                return ;
            }
            if(val==a[p].val){
                a[p].cnt++;
                update(p);
                return ;
            }
            if(val<a[p].val){
                Insert(a[p].l,val);
                if(a[p].dat<a[a[p].l].dat) zig(p);
            }
            else{
                Insert(a[p].r,val);
                if(a[p].dat<a[a[p].r].dat) zag(p);
            }
            update(p);
            return ;
        }
        il int GerPre(int val){
            int ans=1,p=root;
            while(p){
                if(val==a[p].val){
                    if(a[p].l){
                        p=a[p].l;
                        while(a[p].r) p=a[p].r;
                        ans=p;
                    }
                    break;
                }
                if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
                p=val<a[p].val?a[p].l:a[p].r;
            }
            return a[ans].val;
        }
        il int GetNext(int val){
            int ans=2,p=root;
            while(p){
                if(val==a[p].val){
                    if(a[p].r){
                        p=a[p].r;
                        while(a[p].l) p=a[p].l;
                        ans=p;
                    }
                    break;
                }
                if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
                p=val<a[p].val?a[p].l:a[p].r;
            }
            return a[ans].val;
        }
        il void Remove(int &p,int val){
            if(!p) return ;
            if(val==a[p].val){
                if(a[p].cnt>1){
                    a[p].cnt--,update(p);
                    return ;
                }
                if(a[p].l||a[p].r){
                    if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat) zig(p),Remove(a[p].r,val);
                    else zag(p),Remove(a[p].l,val);
                    update(p);
                }
                else p=0;
                return ;
            }
            val<a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
            update(p);
            return ;
        }
}t;
int last;
int mem;
int main(){
    srand(0);
    t.build();
    n=read(),m=read();
    _for(i,1,n) t.Insert(t.root,read());
    while(m--){
        int opt=read(),x=read();
        x^=last;
        int ans;
        switch(opt){
            case 1:
                t.Insert(t.root,x);
                break ;
            case 2:
                t.Remove(t.root,x);
                break ;
            case 3:
                ans=t.GetRankByVal(t.root,x)+1;
                mem^=ans,last=ans;
                break ;
            case 4:
                ans=t.GetValByRank(t.root,x+1);
                mem^=ans,last=ans;
                break ;
            case 5:
                ans=t.GerPre(x);
                mem^=ans,last=ans;
                break ;
            case 6:
                ans=t.GetNext(x);
                mem^=ans,last=ans;
                break ;
        }
    }
    printf("%d\n",mem);
    return 0;
}