Splay TLE 求助

如题 简洁明了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 1100005
using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,tot,rt;
int fa[maxn],size[maxn],ch[maxn][2],val[maxn],cnt[maxn];

inline void maintain(int p)
{
    size[p]=size[ch[p][0]]+size[ch[p][1]]+cnt[p];
}

inline bool get(int p)
{
    return p==ch[fa[p]][1];
}

inline void clear(int p)
{
    size[p]=ch[p][0]=ch[p][1]=val[p]=fa[p]=cnt[p]=0;
}

inline void rotate(int p)
{
    int father=fa[p],grand_father=fa[father],tmp=get(p);
    ch[father][tmp]=ch[p][tmp^1];
    fa[ch[p][tmp^1]]=father;
    ch[p][tmp^1]=father;
    fa[father]=p;
    fa[p]=grand_father;
    if(grand_father) ch[grand_father][father==ch[grand_father][1]]=p;
    maintain(father);
    maintain(p);
}

inline void splay(int p)
{
    for(int f=fa[p];f=fa[p],f;rotate(p))
        if(fa[f]) rotate(get(p)==get(f)?f:p);
    rt=p;
}

inline void insert(int k)
{
    if(!rt)
    {
        val[++tot]=k;
        cnt[tot]++;
        rt=tot;
        maintain(tot);
        return;
    }
    int p=rt,f=0;
    while(1)
    {
        if(val[p]==k)
        {
            cnt[p]++;
            maintain(p);
            maintain(f);
            splay(p);
            return;
        }
        f=p;
        p=ch[p][val[p]<k];
        if(!p)
        {
            val[++tot]=k;
            cnt[tot]++;
            fa[tot]=f;
            ch[f][val[f]<k]=tot;
            maintain(tot);
            maintain(f);
            splay(tot);
            return;
        }
    }
}

inline int rk(int k)
{
    int p=rt,res=0;
    while(1)
    {
        if(k<val[p])
            p=ch[p][0];
        else
        {
            res+=size[ch[p][0]];
            if(k==val[p])
            {
                splay(p);
                return res+1;
            }
            res+=cnt[p];
            p=ch[p][1];
        }
    }
}

inline int kth(int k)
{
    int p=rt;
    while(1)
    {
        if(ch[p][0]&&k<=size[ch[p][0]])
            p=ch[p][0];
        else
        {
            k-=size[ch[p][0]]+cnt[p];
            if(k<=0) return val[p];
            p=ch[p][1];
        }
    }
}

inline int pre()
{
    int p=ch[rt][0];
    while(ch[p][1]) p=ch[p][1];
    return p;
}

inline int nxt()
{
    int p=ch[rt][1];
    while(ch[p][0]) p=ch[p][0];
    return p;
}

inline void delete_val(int k)
{
    rk(k);
    int p=rt;
    if(cnt[p]>1)
    {
        cnt[p]--;
        maintain(p);
        return;
    }
    if(!ch[p][0]&&!ch[p][1])
    {
        clear(p);
        rt=0;
        return;
    }
    if(!ch[p][0])
    {
        rt=ch[p][1];
        fa[rt]=0;
        clear(p);
        return;
    }
    if(!ch[p][1])
    {
        rt=ch[p][0];
        fa[rt]=0;
        clear(p);
        return;
    }
    int pr=pre();
    splay(pr);
    ch[pr][1]=ch[p][1];
    fa[ch[p][1]]=pr;
    clear(p);
    maintain(rt);
}

int main()
{
    //freopen("P6136.in","r",stdin);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int k=read();
        insert(k);
    }
    int opt,x,last=0,ans=0;
    while(m--)
    {
        opt=read(),x=read()^last;
        if(opt==1) insert(x);
        else if(opt==2) delete_val(x);
        else if(opt==3)
        {
            insert(x);
            last=rk(x);
            delete_val(x);
            ans^=last;
        }
        else if(opt==4)
        {
            last=kth(x);
            ans^=last;
        }
        else if(opt==5)
        {
            insert(x);
            last=val[pre()];
            delete_val(x);
            ans^=last;
        }
        else
        {
            insert(x);
            last=val[nxt()];
            delete_val(x);
            ans^=last;
        }
    }
    printf("%d\n",ans);
    return 0;
}