带旋Treap WA+MLE求调

rt，给个hack也可以 qwq

#include <bits/stdc++.h>
#define il inline
#define rg register
#define hh putchar('\n')
#define write(x) printf("%d",x)
using namespace std;

il 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^48);ch=getchar();}
    return x*f;
}

const int M=1e6+10;
int cnt=0;
struct node{
    int ls,rs;
    int key,pri;
    int size; 
}t[M];

il void newNode(int x){
    cnt++;
    t[cnt].size=1;
    t[cnt].ls=t[cnt].rs=0;
    t[cnt].key=x;
    t[cnt].pri=rand();
}

il void Update(int u){
    t[u].size=t[t[u].ls].size+t[t[u].rs].size+1;
}

void rotate(int &o,int d){
    int k;
    if(d==1){
        k=t[o].rs;
        t[o].rs=t[k].ls;
        t[k].ls=o;
    }else{
        k=t[o].ls;
        t[o].ls=t[k].rs;
        t[k].rs=o;
    }
    t[k].size=t[o].size;
    Update(o);
    o=k;
}

void Insert(int &u, int x){
    if(u==0){newNode(x);u=cnt;return;}
    t[u].size++;
    if(x>=t[u].key) Insert(t[u].rs,x);
    else Insert(t[u].ls,x);
    if(t[u].ls!=0 and t[u].pri>t[t[u].ls].pri) rotate(u,0);
    if(t[u].rs!=0 and t[u].pri>t[t[u].rs].pri) rotate(u,1);
    Update(u);
}

void Del(int &u, int x){
    t[u].size--;
    if(t[u].key==x){
        if(t[u].ls==0 and t[u].rs==0){u=0;return;}
        if(t[u].ls==0 or t[u].rs==0){u=t[u].ls+t[u].rs;return;}
        if(t[t[u].ls].pri<t[t[u].rs].pri){rotate(u,0);Del(t[u].rs,x);return;}
        else{rotate(u,1);Del(t[u].ls,x);return;}
    }
    if(t[u].key>=x) Del(t[u].ls,x);
    else Del(t[u].rs,x);
    Update(u);
}

int Rank(int u, int x){
    if(u==0) return 0;
    if(x>t[u].key) return t[t[u].ls].size+1+Rank(t[u].rs,x);
    return Rank(t[u].ls,x);
}

int kth(int u, int k){
    if(k==t[t[u].ls].size+1) return t[u].key;
    if(k>t[t[u].ls].size+1) return kth(t[u].rs,k-t[t[u].ls].size-1);
    if(k<=t[t[u].ls].size) return kth(t[u].ls,k);
}

int pre(int u, int x){
    if(u==0) return 0;
    if(t[u].key>=x) return pre(t[u].ls,x);
    int tmp=pre(t[u].rs,x);
    if(tmp==0) return t[u].key;
    return tmp;
}

int suc(int u, int x){
    if(u==0) return 0;
    if(t[u].key<=x) return suc(t[u].rs,x);
    int tmp=suc(t[u].ls,x);
    if(tmp==0) return t[u].key;
    return tmp;
}

signed main(){
    srand(time(NULL));
    int root=0,n=read(),m=read(),last=0,top=0,ans=0;
    for(int i=1;i<=n;i++){
        int t=read();
        Insert(root,t);
    }
    while(m--){
        int opt=read(),x=read();
        int t;
        if(opt==1){
            Insert(root,x);
        }
        if(opt==2){
            Del(root,x);
        }
        if(opt==3){
            t=Rank(root,x^last)+1;
        }
        if(opt==4){
            t=(kth(root,x^last));
        }
        if(opt==5){
            t=(pre(root,x^last));
        }
        if(opt==6){
            t=suc(root,x^last);
        }
        if(opt>=3){
            top++;
            if(top==1) ans=t;
            else ans^=t;
            last=t;
        }
    }
    write(ans);
    return 0;
}