Splay求调

#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f3f
#define INF 0x7f7f7f7f7f
using namespace std;
namespace Iwara{
    template<class T> T MAX(T x,T y){
        return x>y?x:y;
    }
    template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){
        return MAX(x>y?x:y,arg...);
    }
    template<class T> T MIN(T x,T y){
        return x<y?x:y;
    }
    template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){
        return MIN(x<y?x:y,arg...);
    }
    template<class T> T lowbit(T x){
        return x&-x;
    }
    template<class T> void SWAP(T &x,T &y){
        T qwq;
        qwq=x;
        x=y;
        y=qwq;
        return;
    }
    inline ll read(){
        ll x=0;char ch=getchar();bool fl=false;
        while(!(ch>='0'&&ch<='9')){if(ch=='-')fl=true;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return fl?-x:x;
    }
}
using namespace Iwara;
const ll MAXN=3e6+5;
namespace Splay{
    ll rt=0,tot=0,fa[MAXN],ch[MAXN][2],val[MAXN],cnt[MAXN],sz[MAXN];
    void maintain(ll x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];return;}
    bool getc(ll x){return x==ch[fa[x]][1];}
    void clear_p(ll x){fa[x]=ch[x][0]=ch[x][1]=val[x]=cnt[x]=sz[x]=0;return;}
    void rotate_p(ll x){
        ll y=fa[x],z=fa[y],ch_x=getc(x),ch_y=getc(y);
        ch[y][ch_x]=ch[x][ch_x^1];
        if(ch[x][ch_x^1])fa[ch[x][ch_x^1]]=y;
        ch[x][ch_x^1]=y;
        fa[y]=x;
        fa[x]=z;
        if(z)ch[z][ch_y]=x;
        maintain(y);
        maintain(x);
        return;
    }
    void splay(ll x){
        for(int f=fa[x];f=fa[x],f;rotate_p(x)){
            if(fa[f]){
                if(getc(x)==getc(f))rotate_p(f);
                else rotate_p(x);
            }
        }
        rt=x;
        return;
    }
    void ins(ll x){
        if(!rt){
            val[++tot]=x;
            cnt[tot]++;
            rt=tot;
            maintain(rt);
            return;
        }
        ll cur=rt,f=0;
        while(1){
            if(val[cur]==x){
                cnt[cur]++;
                maintain(cur);
                maintain(f);
                splay(cur);
                break;
            }
            f=cur;
            cur=ch[cur][x>val[cur]];
            if(!cur){
                val[++tot]=x;
                cnt[tot]++;
                fa[tot]=f;
                ch[f][x>val[cur]]=tot;
                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
        return;
    }
    ll rk(ll x){
        ll ans=0,cur=rt;
        while(1){
            if(x<val[cur])cur=ch[cur][0];
            else{
                ans+=sz[ch[cur][0]];
                if(val[cur]==x){
                    splay(cur);
                    return ans+1;
                }
                ans+=cnt[cur];
                cur=ch[cur][1];
            }
        }
    }
    ll kth(ll x){
        ll cur=rt;
        while(1){
            if(ch[cur][0]&&x<=sz[ch[cur][0]])cur=ch[cur][0];
            else{
                x-=cnt[cur]+sz[ch[cur][0]];
                if(x<=0){
                    splay(cur);
                    return val[cur];
                }
                cur=ch[cur][1];
            }
        }
    }
    ll pre(){
        ll cur=ch[rt][0];
        if(!cur)return cur;
        while(ch[cur][1])cur=ch[cur][1];
        splay(cur);
        return cur;
    }
    ll nxt(){
        ll cur=ch[rt][1];
        if(!cur)return cur;
        while(ch[cur][0])cur=ch[cur][0];
        splay(cur);
        return cur;
    }
    void del(ll x){
        rk(x);
        if(cnt[rt]>1){
            cnt[rt]--;
            maintain(rt);
            return;
        }
        if(!ch[rt][0]&&!ch[rt][1]){
            clear_p(rt);
            rt=0;
            return;
        }
        if(!ch[rt][0]){
            ll cur=rt;
            rt=ch[rt][1];
            fa[rt]=0;
            clear_p(cur);
            return;
        }
        if(!ch[rt][1]){
            ll cur=rt;
            rt=ch[rt][0];
            fa[rt]=0;
            clear_p(cur);
            return;
        }
        ll cur=rt,reg=pre();
        fa[ch[cur][1]]=reg;
        ch[reg][1]=ch[cur][1];
        clear_p(cur);
        maintain(rt);
        return;
    }
}
using namespace Splay;
ll n,m;
ll op,x,last,qwq;
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        x=read();
        ins(x);
    }
    while(m--){
        op=read(),x=read();
        x^=last;
        switch(op){
            case 1:
                ins(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                ins(x);
                last=rk(x);
                del(x);
                qwq^=last;
                break;
            case 4:
                last=kth(x);
                qwq^=last;
                break;
            case 5:
                ins(x);
                last=val[pre()];
                del(x);
                qwq^=last;
                break;
            case 6:
                ins(x);
                last=val[nxt()];
                del(x);
                qwq^=last;
                break;
        }
    }
    cout<<qwq;
    return 0;
}

10pts，其余TLE
求调