Splay TLE#7 求条

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,c,u,v,num,ans;
struct Splay
{
    #define N 2200022
    int cnt,root;
    int fa[N],num[N],siz[N],val[N],sons[N][2];
    il void pushup(int x)
    {
        siz[x]=siz[sons[x][0]]+siz[sons[x][1]]+num[x];
    }
    il void del(int x)
    {
        fa[x]=siz[x]=sons[x][0]=sons[x][1]=val[x]=num[x]=0;
    }
    il int faso(int x)
    {
        return sons[fa[x]][0]==x?0:1;
    }
    il void rotate(int x)
    {
        ri y=fa[x],z=fa[y],pl=faso(x);
        sons[y][pl]=sons[x][pl^1];
        if(sons[x][pl^1])
        {
            fa[sons[x][pl^1]]=y;
        }
        sons[x][pl^1]=y;
        fa[y]=x;
        fa[x]=z;
        if(z)
        {
            pl=(y==sons[z][0]?0:1);
            sons[z][pl]=x;
        }
        pushup(y);
        pushup(x);
        return;
    }
    il void splay(int x,int y)
    {
        if(!y)
        {
            root=x;
        }
        while(fa[x]!=y)
        {
            int u=fa[x],v=fa[u];
            if(v!=y)
            {
                int pl=(faso(x)==faso(u)?u:x);
                rotate(pl);
            }
            rotate(x);
        }
        return;
    }
    il void push(int x)
    {
        if(!root)
        {
            cnt++;
            val[cnt]=x;
            num[cnt]++;
            root=cnt;
            pushup(root);
            return;
        }
        ri pl=root,y=0;
        while(1)
        {
            if(val[pl]==x)
            {
                num[pl]++;
                pushup(pl);
                pushup(y);
                splay(pl,0); 
                return;
            }
            y=pl;
            val[pl]<x?pl=sons[pl][1]:pl=sons[pl][0];
            if(!pl)
            {
                cnt++;
                val[cnt]=x;
                num[cnt]++;
                fa[cnt]=y;
                val[y]<x?sons[y][1]=cnt:sons[y][0]=cnt;
                pushup(cnt);
                pushup(y);
                splay(cnt,0);
                return;
            }
        }
    }
    il int rank(int x)
    {
        ri rn=0,pl=root;
        while(1)
        {
            if(x<val[pl])
            {
                pl=sons[pl][0];
                continue;
            }
            rn+=siz[sons[pl][0]];
            if(!pl)
            {
                rn++;
                return rn;
            }
            if(x==val[pl])
            {
                splay(pl,0);
                rn++;
                return rn;
            }
            rn+=num[pl];
            pl=sons[pl][1];
        }
    }
    il void pop(int x)
    {
        rank(x);
        if(num[root]>1)
        {
            num[root]--;
            pushup(root);
            return;
        }
        if(!sons[root][0]&&!sons[root][1])
        {
            del(root);
            root=0;
            return;
        }
        ri pl=root;
        if(!sons[root][0])
        {
            root=sons[root][1];
            fa[root]=0;
            del(pl);
            return;
        }
        if(!sons[root][1])
        {
            root=sons[root][0];
            fa[root]=0;
            del(pl);
            return;
        }
        ri y;
        if(!sons[root][0])
        {
            y=root;
        }
        y=sons[root][0];
        while(sons[y][1])
        {
            y=sons[y][1];
        }
        splay(y,0);
        fa[sons[pl][1]]=y;
        sons[y][1]=sons[pl][1];
        del(pl);
        pushup(root);
    }
    il int kth(int x)
    {
        ri pl=root;
        while(1)
        {
            if(sons[pl][0]!=0&&x<=siz[sons[pl][0]])
            {
                pl=sons[pl][0];
                continue;
            }
            x-=siz[sons[pl][0]];
            if(x<=num[pl])
            {
                splay(pl,0);
                return val[pl];
            }
            x-=num[pl];
            pl=sons[pl][1];
        }
    }
    il int pre(int x)
    {
        (*this).push(x);
        if(!sons[root][0])
        {
            return -inf;
        }
        ri pl=sons[root][0];
        while(sons[pl][1])
        {
            pl=sons[pl][1];
        }
        ri rn=val[pl];
        (*this).pop(x);
        return rn;
    }
    il int next(int x)
    {
        (*this).push(x);
        if(!sons[root][1])
        {
            return inf;
        }
        ri pl=sons[root][1];
        while(sons[pl][0])
        {
            pl=sons[pl][0];
        }
        ri rn=val[pl];
        splay(pl,0);
        (*this).pop(x);
        return rn;
    }
    #undef N
}tree;
int main()
{
//  freopen("P6136_7.in","r",stdin);
    scanf("%d%d",&a,&b);
    for(ri i=1;i<=a;i++)
    {
        scanf("%d",&c);
        tree.push(c);
    }
    while(b--)
    {
        scanf("%d%d",&u,&v);
        v^=num;
        if(u==1)
        {
            tree.push(v);
            continue;
        }
        if(u==2)
        {
            tree.pop(v);
            continue;
        }
        if(u==3)
        {
            num=tree.rank(v);
//          printf("%d\n",num);
            ans^=num;
            continue;
        }
        if(u==4)
        {
            num=tree.kth(v);
//          printf("%d\n",num);
            ans^=num;
            continue;
        }
        if(u==5)
        {
            num=tree.pre(v);
//          printf("%d\n",num);
            ans^=num;
            continue;
        }
        if(u==6)
        {
            num=tree.next(v);
//          printf("%d\n",num);
            ans^=num;
            continue;
        }
    }
    printf("%d",ans);
    return 0;
}
/*
10 10
10
5
3
7
6
3
9
9
8
8

10 8
10
5
3
7
6
3
9
9

10 10
89 52 65 83 40 23 12 1 20 46 
2 12
3 54
1 58
1 83
2 83
5 66
6 52
4 8
6 78
4 5

*/