Splay52ptsTLE求帮忙,oiwiki写法,普通版已过,码风良好

rt

#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 4000005
#define eps 1e-9
#define foru(a,b,c) for(int a=b;a<=c;a++)
#define RT return 0;
#define LL long long
#define HH printf("\n")
using namespace std;
int n,rt,tot;
struct Node{
    int fa,ch[2],val,cnt,sz;
}tr[MAXN];
void maintain(int x){
    tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].cnt;
}
bool get(int x){
    return x==tr[tr[x].fa].ch[1];
}
void clear(int x){
    tr[x]={0,{0,0},0,0,0};
}
void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa,chk=get(x);
    tr[y].ch[chk]=tr[x].ch[chk^1];
    if(tr[x].ch[chk^1]){
        tr[tr[x].ch[chk^1]].fa=y;
    }
    tr[x].ch[chk^1]=y;
    tr[y].fa=x;
    tr[x].fa=z;
    if(z){
        tr[z].ch[y==tr[z].ch[1]]=x;
    }
    maintain(y);
    maintain(x);
}
void splay(int x){
    for(int f=tr[x].fa;f=tr[x].fa;rotate(x)){
        if(tr[f].fa)    rotate(get(x)==get(f)?f:x);
    }
    rt=x;
}
void insert(int k){
    if(!rt){
        tr[++tot].val=k;
        tr[tot].cnt++;
        rt=tot;
        maintain(rt);
        return ;
    }
    int cur=rt,f=0;
    while(1){
        if(tr[cur].val==k){
            tr[cur].cnt++;
            maintain(cur);
            maintain(f);
            splay(cur);
            break;
        }
        f=cur;
        cur=tr[cur].ch[tr[cur].val<k];
        if(!cur){
            tr[++tot].val=k;
            tr[tot].cnt++;
            tr[tot].fa=f;
            tr[f].ch[tr[f].val<k]=tot;
            maintain(tot);
            maintain(f);
            splay(tot);
            break;
        }
    }
}
int rk(int k){
    int res=0,cur=rt;
    while(1){
        if(k<tr[cur].val){
            cur=tr[cur].ch[0];
        }else{
            res+=tr[tr[cur].ch[0]].sz;
            if(k==tr[cur].val){
                splay(cur);
                return res+1;
            }
            res+=tr[cur].cnt;
            cur=tr[cur].ch[1];
        }
    }
}
int kth(int k){
    int cur=rt;
    while(1){
        if(tr[cur].ch[0] && k<=tr[tr[cur].ch[0]].sz){
            cur=tr[cur].ch[0];
        }else{
            k-= tr[cur].cnt + tr[tr[cur].ch[0]].sz;
            if(k<=0){
                splay(cur);
                return tr[cur].val;
            }
            cur=tr[cur].ch[1];
        }
    }
}
int pre(){
    int cur=tr[rt].ch[0];
    if(!cur)    return cur;
    while(tr[cur].ch[1]){
        cur=tr[cur].ch[1];
    }
    splay(cur);
    return cur;
}
int nxt(){
    int cur=tr[rt].ch[1];
    if(!cur)    return cur;
    while(tr[cur].ch[0]){
        cur=tr[cur].ch[0];
    }
    splay(cur);
    return cur;
}
void del(int k){
    rk(k);
    if(tr[rt].cnt>1){
        tr[rt].cnt--;
        maintain(rt);
        return ;
    }
    if(!tr[rt].ch[0] && !tr[rt].ch[1]){
        clear(rt);
        rt=0;
        return ;
    }
    if(!tr[rt].ch[0]){
        int cur=rt;
        rt=tr[rt].ch[1];
        tr[rt].fa=0;
        clear(cur);
        return ;
    }
    if(!tr[rt].ch[1]){
        int cur=rt;
        rt=tr[rt].ch[0];
        tr[rt].fa=0;
        clear(cur);
        return ;
    }
    int cur=rt,x=pre();
    tr[tr[cur].ch[1]].fa=x;
    tr[x].ch[1]=tr[cur].ch[1];
    clear(cur);
    maintain(rt);
}
int m;
int main(){
    scanf(" %d %d",&n,&m);
    foru(i,1,n){
        int a;
        scanf(" %d",&a);
        insert(a);
    }
    int la=0,ans=0;
    while(m--){
        int opt,x;
        scanf(" %d %d",&opt,&x);
        x^=la;
        if(opt==1){
            insert(x);
        }else if(opt==2){
            del(x);
        }else if(opt==3){
            insert(x);
            la=rk(x);
            del(x);
            ans^=la;
        }else if(opt==4){
            insert(x);
            la=kth(x);
            ans^=la;
            del(x);
        }else if(opt==5){
            insert(x);
            la=tr[pre()].val;
            ans^=la;
            del(x);
        }else if(opt==6){
            insert(x);
            la=tr[nxt()].val;
            ans^=la;
            del(x);
        }
    }
    printf("%d",ans);
    return 0;
}