splay 求卡常 88分 马峰良好

#include<bits/stdc++.h>
using namespace std;
const int N=11e5+10;
int n,m,last,ans;
int rt,tot;
int fa[N],ch[N][2],val[N],cnt[N],sz[N];
bool get(int x) {return ch[fa[x]][1]==x;}
void pushup(int x) {
    if(x) {
        sz[x]=cnt[x];
        if(ch[x][0]) sz[x]+=sz[ch[x][0]];
        if(ch[x][1]) sz[x]+=sz[ch[x][1]];
    }
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    ch[y][k]=ch[x][k^1]; fa[ch[x][k^1]]=y;
    ch[x][k^1]=y; fa[y]=x;
    fa[x]=z;
    if(z) ch[z][ch[z][1]==y]=x;
    pushup(y); pushup(x);
}
void splay(int x,int goal=0) {
    for(; fa[x]!=goal; ) {
        int y=fa[x],z=fa[y];
        if(z!=goal) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
    if(goal==0) rt=x;
}
void find(int x) {
    int u=rt;
    if(!u) return ;
    for(; ch[u][x>val[u]]&&x!=val[u]; )
        u=ch[u][x>val[u]];
    splay(u,0);
}
void insert(int x) {
    int u=rt,f=0;
    for(; u&&val[u]!=x; ) {
        f=u;
        u=ch[u][x>val[u]];
    }
    if(u) {cnt[u]++; pushup(u); pushup(f);}
    else {
        u=++tot;
        val[u]=x; sz[u]=cnt[u]=1;
        fa[u]=f; ch[u][0]=ch[u][1]=0;
        if(f) {ch[f][x>val[f]]=u; pushup(f);}
        else rt=u;
    }
    splay(u,0);
}
int query_rank(int x) {
    find(x);
    if(val[rt]>=x) return sz[ch[rt][0]]+1;
    else return sz[ch[rt][0]]+cnt[rt]+1;
}
int query_kth(int x) {
    int u=rt;
    for(; ; ) {
        if(ch[u][0]&&x<=sz[ch[u][0]])
            u=ch[u][0];
        else {
            int tmp=sz[ch[u][0]]+cnt[u];
            if(x<=tmp) return val[u];
            x-=tmp; u=ch[u][1]; 
        }
    }
}
int pre(int x) {
    find(x);
    if(val[rt]<x) return rt;
    int u=ch[rt][0];
    for(; ch[u][1]; ) u=ch[u][1];
    return u;
}
int succ(int x) {
    find(x);
    if(val[rt]>x) return rt;
    int u=ch[rt][1];
    for(; ch[u][0]; ) u=ch[u][0];
    return u;
}
void del(int x) {
    find(x);
    if(cnt[rt]>1) {cnt[rt]--; pushup(rt); return ;}
    if(!ch[rt][0]&&!ch[rt][1]) {rt=0; return ;}
    if(!ch[rt][0]||!ch[rt][1]) {
        rt=ch[rt][0]?ch[rt][0]:ch[rt][1];
        fa[rt]=0;
        return ;
    }
    int ort=rt,p=pre(x);
    splay(p);
    ch[rt][1]=ch[ort][1]; fa[ch[ort][1]]=rt;
    pushup(rt);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int x; n--; ) {
        scanf("%d",&x);
        insert(x);
    }
    for(int op,x; m--; ) {
        scanf("%d%d",&op,&x);
        x^=last;
        switch(op) {
            case 1: insert(x); break;
            case 2: del(x); break;
            case 3: last=query_rank(x); ans^=last; break;
            case 4: last=query_kth(x); ans^=last; break;
            case 5: last=val[pre(x)]; ans^=last; break;
            case 6: last=val[succ(x)]; ans^=last; break;
        }
    }
    printf("%d\n",ans);
    return 0;
}