请求加强数据

RT

先maintain(fa[x])再maintain(x)居然没卡掉

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5; 
int n,m;
int op,qwq;
struct Splay{
    int rt,tot,fa[MAXN],sz[MAXN],son[MAXN][2],val[MAXN],cnt[MAXN];
    void pre(){
        rt=tot=0;
        memset(fa,0,sizeof(fa));
        memset(sz,0,sizeof(sz));
        memset(son,0,sizeof(son));
        memset(val,0,sizeof(val));
        memset(cnt,0,sizeof(cnt));
        return;
    }
    void maintain(int x){
        sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
        return;
    }
    bool get(int x){
        return x==son[fa[x]][1];
    }
    void clear(int x){
        fa[x]=sz[x]=son[x][0]=son[x][1]=val[x]=cnt[x]=0;
        return;
    }
    void rotate(int x){
        int Y=fa[x],Z=fa[Y],son_type=get(x);
        son[Y][son_type]=son[x][son_type^1];
        if(son[x][son_type^1])fa[son[x][son_type^1]]=Y;
        son[x][son_type^1]=Y;
        fa[Y]=x;
        fa[x]=Z;
        if(Z)son[Z][Y==son[Z][1]]=x;
        maintain(x),maintain(Y);//这里写反了，但是它居然AC了
        return;
    }
    void splay(int x){
        for(int f=fa[x];f=fa[x],f;rotate(x))if(fa[f])rotate(get(f)==get(x)?f:x);
        rt=x;
        return;
    }
    void insert(int x){
        if(!rt){
            val[++tot]=x;
            cnt[tot]++;
            rt=tot;
            maintain(rt);
            return;
        }
        int now=rt,father=0;
        while(1){
            if(val[now]==x){
                cnt[now]++;
                maintain(now);
                maintain(father);
                splay(now);
                return;
            }
            father=now;
            now=son[now][val[now]<x];
            if(!now){
                val[++tot]=x;
                cnt[tot]++;
                fa[tot]=father;
                son[father][val[father]<x]=tot;
                maintain(tot);
                maintain(father);
                splay(tot);
                return;
            } 
        }
        return;
    }
    int rk(int x){
        int ans=0,now=rt;
        while(1){
            if(!now)return ans+1;
            if(x<val[now])now=son[now][0];
            else{
                ans+=sz[son[now][0]];
                if(val[now]==x){
                    splay(now);
                    return ans+1;
                }
                ans+=cnt[now];
                now=son[now][1];
            } 
        } 
    }
    int kth(int x){
        int now=rt;
        while(1){
            if(son[now][0]&&x<=sz[son[now][0]])now=son[now][0];
            else{
                x-=sz[son[now][0]]+cnt[now];
                if(x<=0){
                    splay(now);
                    return val[now];
                }
                now=son[now][1];
            }
        }
    } 
    int lst(){
        int now=son[rt][0];
        if(!now)return now;
        while(son[now][1])now=son[now][1];
        splay(now);
        return now;
    }
    int nxt(){
        int now=son[rt][1];
        if(!now)return now;
        while(son[now][0])now=son[now][0];
        splay(now);
        return now;
    }
    void erase(int x){
        rk(x);
        if(cnt[rt]>1){
            cnt[rt]--;
            maintain(rt);
            return;
        }
        if(!son[rt][0]&&!son[rt][1]){
            clear(rt);
            rt=0;
            return;
        }
        if(!son[rt][0]){
            int now=rt;
            rt=son[now][1];
            fa[rt]=0;
            clear(now);
            return;
        }
        if(!son[rt][1]){
            int now=rt;
            rt=son[now][0];
            fa[rt]=0;
            clear(now);
            return;
        }
        int now=rt,new_x=lst();
        fa[son[now][1]]=new_x;
        son[new_x][1]=son[now][1];
        clear(now);
        maintain(rt);
        return;
    }
}S;
int last,ans;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    S.pre();
    for(int i=1;i<=n;i++){
        cin>>qwq;
        S.insert(qwq);
    }
    while(m--){
        cin>>op>>qwq;
        qwq^=last;
        switch(op){
            case 1:S.insert(qwq);break;
            case 2:S.erase(qwq);break;
            case 3:last=S.rk(qwq);ans^=last;break;
            case 4:last=S.kth(qwq);ans^=last;break;
            case 5:S.insert(qwq);last=S.val[S.lst()];ans^=last;S.erase(qwq);break;
            case 6:S.insert(qwq);last=S.val[S.nxt()];ans^=last;S.erase(qwq);break;
        } 
    }
    cout<<ans;
    return 0;
}