splay 88pts TLE on #1#2#17

P6136 【模板】普通平衡树（数据加强版）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ll int 
const int MAXN=1e6+10,INTMIN=-1e18,INTMAX=1e18;
template<typename T>inline void readT(T &x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
struct Splay{
    int fa[MAXN],sz[MAXN],ch[MAXN][2],cnt,root;
    ll key[MAXN];
    Splay(){
        root=newnode(INTMIN);
        link(root,newnode(INTMAX),1);
    }
    inline int newnode(ll k){
        ++cnt;
        key[cnt]=k;
        sz[cnt]=1;
        return cnt;
    }
    inline void update(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    }
    //y成为x的w方向儿子 
    inline void link(int x,int y,int w){
        ch[x][w]=y;
        if(y)fa[y]=x;
    }
    inline int getlr(int x,int y){
        return ch[x][1]==y;
    }
    inline void rot(int x,int w){//node x,w 0/1 left/right rotate 
        int z=fa[x],s=ch[x][w^1];
        link(x,ch[s][w],w^1); 
        link(s,x,w);
        if(z)link(z,s,getlr(z,x));
        else fa[s]=0,root=s;
        update(x);
    }
    void splay(int x,int tar){//x splay to target below 
        while(1){//双旋存在 
        if(fa[x]==tar||fa[fa[x]]==tar)break;
        int fw=getlr(fa[x],x),gw=getlr(fa[fa[x]],fa[x]);//father grandfather
        fw==gw?(rot(fa[fa[x]],gw^1),rot(fa[x],fw^1))
            :(rot(fa[x],fw^1),rot(fa[x],gw^1));//in the right 爷爷 已经转下来了
        }
        if(fa[x]!=tar)rot(fa[x],getlr(fa[x],x)^1);
        update(x);
    }
    void insert(ll v){
        int p=root,q;//q上一个节点 
        while(p){
            q=p;
            p=ch[p][v>key[p]]; 
        }
        int x=newnode(v);
        link(q,x,v>key[q]);
        update(q);
        splay(x,0);
    }
    void erase(ll v){
        int p=find(v);
        if(!p)return ;
        int x=ch[p][0],y=ch[p][1];
        while(ch[x][1])x=ch[x][1];
        splay(x,0);
        while(ch[y][0])y=ch[y][0];
        splay(y,x);
        ch[y][0]=0;//cut link 
        update(y);
        update(x);
    }
    int find(ll v){
        int p=root;
        while(p&&key[p]!=v)
            p=ch[p][v>key[p]];
        splay(p,0);
        return p;
    }
    int rank(ll v){
        int ans=0,q,p=root;
        while(p){
            q=p;
            if(key[p]<v)ans+=sz[ch[p][0]]+1,p=ch[p][1];
            else p=ch[p][0];
        }
        splay(q,0);
        return ans;
    }
    ll kth_element(int k){
        k++;
        int p=root;
        while(p){
            if(sz[ch[p][0]]>=k)p=ch[p][0];
            else{
                k-=sz[ch[p][0]]+1;
                if(k==0)break;
                p=ch[p][1];
            }
        }
        splay(p,0);
        return key[p];
    }
    ll prev(ll v){
        ll ans,q,p=root;
        while(p){
            q=p;
            if(key[p]<v)ans=key[p],p=ch[p][1];
            else p=ch[p][0];
        }
        splay(q,0);
        return ans;
    }
    ll succ(ll v){
        ll ans,q,p=root;
        while(p){
            q=p;
            if(key[p]>v)ans=key[p],p=ch[p][0];
            else p=ch[p][1];
        }
        splay(q,0);
        return ans; 
    }
//  inline void debug(int x){
//      if(!x)return ;
//      debug(ch[x][0]);
//      cout<<key[x]<<" ";
//      if(key[x]==INT32_MIN) cout<<"\n";
//      debug(ch[x][1]);
//  }
}splay;

int main(){
    int n,m;
    ll l=0,x,ans=0;
    readT(n),readT(m); 
    for(register int i=1;i<=n;++i)readT(x),splay.insert(x);
    while(m--){
        ll op,v;
        readT(op),readT(v);
        if(op==1)v^=l,splay.insert(v);
        else if(op==2)v^=l,splay.erase(v);
        else if(op==3)v^=l,l=splay.rank(v),ans^=l;
        else if(op==4)v^=l,l=splay.kth_element(v),ans^=l;
        else if(op==5)v^=l,l=splay.prev(v),ans^=l;
        else v^=l,l=splay.succ(v),ans^=l;
        //splay.debug(splay.root);
    }
    cout<<ans;
}