孩子太难了求助卡常技巧

Splay板子

救救孩子吧，卡常卡了一下午了

浪费评测资源

不过我发现有些时候不Splay更快？？？

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e+6+100;
const int inf = 0x7f7f7f7f;
int n,m,la,ans;
int f[maxn],ch[maxn][2],val[maxn],cnt[maxn],siz[maxn];
int rt,tot;

int read(){
    int v=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
    return v*f;
}
void pushup(int x){
    siz[x] = siz[ch[x][0]]+cnt[x]+siz[ch[x][1]];
}
int get(int x){
    return x==ch[f[x]][1];
}
void connect(int s,int fa,int dir){
    f[s] = fa;
    ch[fa][dir] = s;
}
void rotate(int x){
    int fa=f[x],gfa=f[fa];
    int s1=get(x),s2=get(fa);
    int s=ch[x][s1^1];
    connect(s,fa,s1);
    connect(x,gfa,s2);
    connect(fa,x,s1^1);
    pushup(fa);
    pushup(x); 
}
void Splay(int x,int gol){
    for(int fa;(fa=f[x])&&fa!=gol;rotate(x)){
        if(f[fa]!=gol) rotate(get(x)==get(fa)?fa:x);
    }
    if(!gol) rt = x;
}
void find(int x){
    int cur=rt;
    while(ch[cur][x>val[cur]]&&val[cur]!=x)  cur = ch[cur][x>val[cur]];
    Splay(cur,0);
}
int pre(int x){
    find(x);
    if(val[rt]<x) return rt;
    int cur=ch[rt][0];
    while(ch[cur][1]) cur = ch[cur][1];
    return cur;
}
int suc(int x){
    find(x);
    if(val[rt]>x) return rt;
    int cur=ch[rt][1];
    while(ch[cur][0]) cur = ch[cur][0];
    return cur;
}
int rank(int x){
    int cur=rt,rk=0;
    while(cur){
        if(val[cur]<x){
            rk += siz[ch[cur][0]]+cnt[cur];
            cur=ch[cur][1];
        }
        else if(val[cur]>x){
            cur=ch[cur][0];
        }
        else if(val[cur]==x){
            rk+=siz[ch[cur][0]];
            break;
        }
    }
    //Splay(cur,0);
    //if(cur) ++rk; 
    return rk;
}
int kth(int k){
    int cur=rt;
    while(true){
        if(k<=siz[ch[cur][0]]) cur=ch[cur][0];
        else if(k>siz[ch[cur][0]]+cnt[cur]) k-=siz[ch[cur][0]]+cnt[cur],cur=ch[cur][1];
        else{
            //Splay(cur,0);
            return cur;
        }
    }
}
void ins(int x){
    int cur=rt,fa=0;
    while(cur&&val[cur]!=x){
        fa=cur;
        cur=ch[cur][x>val[cur]]; 
    }
    if(cur){
        ++cnt[cur];
    }
    else{
        cur= ++tot;
        val[cur] = x;
        siz[cur] = cnt[cur] = 1;
        f[cur] = fa;
        if(fa) ch[fa][x>val[fa]] = cur;
    }
    Splay(cur,0);
}
void del(int x){
    int lst=pre(x),nxt=suc(x);
    Splay(lst,0);
    Splay(nxt,lst);
    int cur = ch[nxt][0];
    if(cnt[cur]>1){
        --cnt[cur];
        Splay(cur,0);
    }else{
        ch[nxt][0]=0;
        f[cur]=siz[cur]=cnt[cur]=ch[cur][0]=ch[cur][1]=0;
        pushup(nxt);
        pushup(lst);
    }
}
int main(){
    //freopen("61361.in","r",stdin);
    //freopen("ddd.out","w",stdout);
    n=read();m=read();
    ins(inf);ins(-inf);
    for(register int i=1;i<=n;++i){
        int x = read();
        ins(x);
    }
    //printf("ccf\n");
    for(register int i=1;i<=m;++i){
        //if(i)printf("ccf %d %d\n",i,la);
        int opt=read(),x=read()^la;
        if(opt==1) ins(x);
        if(opt==2) del(x);
        if(opt<=2) continue;
        if(opt==3) la=rank(x);
        if(opt==4) la=val[kth(x+1)];
        if(opt==5) la=val[pre(x)];
        if(opt==6) la=val[suc(x)];
        ans ^= la;
        //printf("%d\n",la);
    }
    printf("%d\n",ans);
    return 0;
}