splay板子 RE*7,TLE*3，求调

RT

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 200005;
#define root t[0].ch[1]
long long tot;
struct tree
{
    long long w;
    long long fa;
    long long ch[2];
    long long cnt;
    long long size;
}t[maxn];
void update(long long x)
{
    t[x].size=t[x].cnt+t[t[x].ch[0]].size+t[t[x].ch[1]].size;
}
long long ff(long long x)
{
    return t[t[x].fa].ch[1]==x;
}
void connect(long long x,long long y,long long now)
{
    t[y].ch[now]=x;
    t[x].fa=y;
}
void ronate(long long x)
{
    long long y=t[x].fa;
    long long z=t[y].fa;
    long long ys=ff(y);
    long long xs=ff(x);
    connect(t[x].ch[xs^1],y,xs);
    connect(y,x,xs^1);
    connect(x,z,ys);
    update(y);
    update(x);
}
void splay(long long x,long long y)
{
    y=t[y].fa;
    while(t[x].fa!=y)
    {
        if(t[t[x].fa].fa==y)ronate(x);
        else if(ff(x)==ff(t[x].fa))ronate(t[x].fa),ronate(x);
        else ronate(x),ronate(x);
    }
}
void newpoint(long long w,long long fa)
{
    tot++;
    t[tot].fa=fa;
    t[tot].w=w;
    t[tot].size = t[tot].cnt = 1;
}
void insert(long long x)
{
    long long now=root;
    if(root==0)
    {
        newpoint(x,0);
        root=tot;
    }else
    {
        while(1)
        {
            t[now].size++;
            if(t[now].w == x)
            {
                t[now].cnt++;
                splay(now,root);
                return;
            }
            long long nxt=x<t[now].w?0:1;
            if(!t[now].ch[nxt])
            {
                newpoint(x,now);
                t[now].ch[nxt]=tot;
                splay(tot,root);
                return;
            }
            now=t[now].ch[nxt];
        }
    }
}
long long find(long long x)
{
    long long now=root;
    while(1)
    {
        if(!now)return 0;
        if(t[now].w==x)
        {
            splay(now,root);
            return now;
        }
        long long nxt= x<t[now].w?0:1;
        now=t[now].ch[nxt];
    }
}
void delet(long long x)
{
    long long pos = find(x);
    if(!pos)return;
    if(t[pos].cnt>1)
    {
        t[pos].size--;
        t[pos].cnt--;
        return;
    }else
    {
        if(!t[pos].ch[0]&&!t[pos].ch[1])
        {
            root=0;
            return;
        }else if(!t[pos].ch[0])
        {
            root=t[pos].ch[1];
            t[root].fa=0;
            return;
        }else if(!t[pos].ch[1])
        {
            root=t[pos].ch[0];
            t[root].fa=0;
        }else if(!t[pos].ch[0])
        {
            root=t[pos].ch[1];
            t[root].fa=0;
        }else
        {
            long long left=t[pos].ch[0];
            while(t[left].ch[1])left=t[left].ch[1];
            splay(left,t[pos].ch[0]);
            connect(t[pos].ch[1],left,1);
            connect(left,0,1);
            update(left);
        }
    }
}
long long rak(long long x)
{
    long long pos=find(x);
    return t[t[pos].ch[0]].size+1;
}
long long arank(long long x)
{
    long long now=root;
    while(1)
    {
        long long used=t[now].size-t[t[now].ch[1]].size;
        if(x>t[t[now].ch[0]].size&&x<=used)
        {
            break;
        }
        if(x<used)
        {
            now=t[now].ch[0];
        }else
        {
            x=x-used;
            now=t[now].ch[1];
        }
    }
    splay(now,root);
    return t[now].w;
}
long long lower(long long x)
{
    long long now=root;
    long long ans=-10000000000000000;
    while(now)
    {
        if(t[now].w<x&&t[now].w>ans)
        {
            ans=t[now].w;
        }
        if(x>t[now].w)now=t[now].ch[1];
        else now=t[now].ch[0];
    }
    return ans;
}
long long upper(long long x)
{
    long long now=root;
    long long ans=10000000000000000;
    while(now)
    {
        if(t[now].w>x&&t[now].w<ans)ans=t[now].w;
        if(x<t[now].w)now=t[now].ch[0];
        else now=t[now].ch[1];
    }
    return ans;
}
int main()
{
    long long n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;i++)
    {
        long long x;
        cin>>x;
        insert(x);
    }
    long long last=0,k=0;
    for(int i=1;i<=m;i++)
    {
        long long x,opt;
        cin>>opt>>x;
        x^=last;
        if(opt==1)
        {
            insert(x);
        }else if(opt ==2)
        {
            delet(x);
        }else if(opt==3)
        {
            if(find(x))
            {
                last=rak(x);
            }else{
                last=rak(lower(x))+1;
            }
        }else if(opt==4)
        {
            last=arank(x);
        }else if(opt==5)
        {
            last=lower(x);
        }else if(opt==6)
        {
            last=upper(x);
        }
        if(opt>=3)k^=last;
    }
    cout<<k;
    return 0;
}