52分Fhq-treap求调教

#include<bits/stdc++.h>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
using namespace std;
const int N=2e6+10;
struct Tree{
    int wei,val,siz,ch[2];
}t[N];
int n,m,tot,root;
int last,ans,a,b,c;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void pushup(int x){
    t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;
}
inline void spilt(int x,int k,int &a,int &b){
    if(!x){
        a=0,b=0;
        return ;
    }
    if(t[x].val<=k){
        a=x;
        spilt(rs(x),k,rs(x),b);
    }
    else{
        b=x;
        spilt(ls(x),k,a,ls(x));
    }
    pushup(x);
}
inline int merge(int x,int y){
    if(!x||!y){
        return x+y;
    }
    if(t[x].wei<=t[y].wei){
        rs(x)=merge(rs(x),y);
        pushup(x);
        return x;
    }
    else{
        ls(y)=merge(x,ls(y));
        pushup(y);
        return y;
    }
}
inline void insert(int k){
    t[++tot].val=k,t[tot].wei=rand();
    t[tot].siz=1;
    spilt(root,k,a,b);
    root=merge(merge(a,tot),b);
}
inline void remove(int k){
    spilt(root,k,a,b);
    spilt(a,k-1,a,c);
    c=merge(ls(c),rs(c));
    root=merge(merge(a,c),b);
}
inline int ck_rk(int k){
    int rank;
    spilt(root,k-1,a,b);
    rank=t[a].siz+1;
    root=merge(a,b);
    return rank;
}
inline int ck_val(int x,int k){
    if(k==t[ls(x)].siz+1){
        return t[x].val;
    }
    if(k<=t[ls(x)].siz){
        return ck_val(ls(x),k);   
    }
    else{
        return ck_val(rs(x),k-t[ls(x)].siz-1); 
    }
}
inline int ck_pre(int x){
    return ck_val(root,ck_rk(x)-1);
}
inline int ck_next(int x){
    return ck_val(root,ck_rk(x+1));
}
int main(){
    int n,m;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        int x;
        x=read();
        insert(x);
    }
    while(m--){
        int op,qwq;
        op=read();
        qwq=read()^last;
        if(op==1){
            insert(qwq);
        }
        else if(op==2){
            remove(qwq);
        } 
        else if(op==3){
            last=ck_rk(qwq);
        }
        else if(op==4){
            last=ck_val(root,qwq);
        }
        else if(op==5){
            last=ck_pre(qwq);
        }
        else if(op==6){
            last=ck_next(qwq);
        }
        ans^=last;
    }
    cout<<ans;
}