普通平衡树加强版 Splay #11TLE

这个代码，我照着我之前的AC记录对了一下，没有找到bug。

下面的一堆注释不用管，是给我自己用的。

代码写的有点丑，见谅。

#include<bits/stdc++.h>
using namespace std;
namespace io 
{
    template<typename T> inline void iread(T &x114){
        char c=' ';int wx114=1;x114=0;
        while(!isdigit(c)){c=getchar();if(c=='-')wx114=-1;}
        while(isdigit(c)){x114=x114*10+c-'0';c=getchar();}
        x114*=wx114;
    }
    template<typename T> inline void write(T x114){
        if(x114==0){putchar('0');return;}
        if(x114<0){putchar('-');x114=-x114;}
        int stk[50],top=0;
        while(x114){stk[++top]=x114%10;x114/=10;}
        while(top) putchar(stk[top--]+'0');
    }
}
const int N=1e7+10;
struct SplayNode
{
    int data;
    int fa;
    int cnt;
    int son[2];
    int siz;
    void init(int father,int val)
    {
        fa=father;
        data=val;
        cnt=siz=1;
    }
}Splay[N];
int root,idx;
int m,n,op,rx,lst,ans,q;
inline void Splay_Pushup(int x)
{
    Splay[x].siz=Splay[Splay[x].son[0]].siz+Splay[Splay[x].son[1]].siz
                  +Splay[x].cnt;
}
inline void Splay_Rotate(int x)
{
    int y=Splay[x].fa,z=Splay[y].fa;
    int k=Splay[y].son[1]==x;
    Splay[y].son[k]=Splay[x].son[k^1];
    Splay[Splay[x].son[k^1]].fa=y;
    Splay[x].son[k^1]=y;
    Splay[y].fa=x;
    Splay[z].son[Splay[z].son[1]==y]=x;
    Splay[x].fa=z;
    Splay_Pushup(y);
    Splay_Pushup(x);
}
inline void Splay_Splay(int x,int k)
{
    while(Splay[x].fa!=k)
    {
        int y=Splay[x].fa,z=Splay[y].fa;
        if(z^k)
            (Splay[y].son[0]==x)^(Splay[z].son[0]==x)?Splay_Rotate(x):Splay_Rotate(y);
        Splay_Rotate(x);
    }
    if(!k) root=x;
}
inline void Splay_Find(int v)
{
    int x=root;
    while(Splay[x].son[v>Splay[x].data]&&Splay[x].data!=v)
        x=Splay[x].son[v>Splay[x].data];
    Splay_Splay(x,0);
}
inline int Splay_GetPre(int v)
{
    Splay_Find(v);
    int x=root;
    if(Splay[x].data<v)
        return x;
    x=Splay[x].son[0];
    while(Splay[x].son[1])
        x=Splay[x].son[1];
    Splay_Splay(x,0);
    return x;
}
inline int Splay_GetSuc(int v)
{
    Splay_Find(v);
    int x=root;
    if(Splay[x].data>v)
        return x;
    x=Splay[x].son[1];
    while(Splay[x].son[0])
        x=Splay[x].son[0];
    Splay_Splay(x,0);
    return x;
}
inline void Splay_Delete(int v)
{
    int pre=Splay_GetPre(v);
    int suc=Splay_GetSuc(v);
    Splay_Splay(pre,0);
    Splay_Splay(suc,pre);
    int x=Splay[suc].son[0];
    if(Splay[x].cnt>1)
        --Splay[x].cnt,Splay_Splay(x,0);
    else
        Splay[suc].son[0]=0,Splay_Splay(suc,0);
}
inline void Splay_Insert(int v)
{
    int x=root,father=0;
    while(x&&Splay[x].data!=v)
    {
        father=x;
        x=Splay[x].son[Splay[x].data<v];
    }
    if(x) ++Splay[x].cnt;
    else
    {
        x=++idx;
        Splay[x].init(father,v);
        Splay[father].son[Splay[father].data<v]=x;
    }
    Splay_Splay(x,0);
}
inline int Splay_GetRank(int v)
{
    Splay_Insert(v);
    int x=root;
    int s=Splay[Splay[x].son[0]].siz;
    Splay_Delete(v);
    return s;
}
inline int Splay_GetVal(int k)
{
    int x=root;
    ++k;
    while(1)
    {
        int y=Splay[x].son[0];
        if(k>Splay[y].siz+Splay[x].cnt)
        {
            k-=Splay[y].siz+Splay[x].cnt;
            x=Splay[x].son[1];
        }
        else if(Splay[y].siz>=k)
            x=y;
        else
            break;
    }
    Splay_Splay(x,0);
    return Splay[x].data;
}
inline void Splay_Create()
{
    Splay_Insert(0x80000000);
    Splay_Insert(0x7fffffff);
}
signed main()
{
    io::iread(m);
    io::iread(n);
    Splay_Create();
    for(int i=1;i<=m;++i)
    {
        io::iread(rx);
        Splay_Insert(rx);
    }
    for(int i=1;i<=n;++i)
    {
        io::iread(op);
        io::iread(rx);
        rx^=lst;
        if(op==1) Splay_Insert(rx);
        else if(op==2) Splay_Delete(rx);
        else if(op==3)
        {
            q=Splay_GetRank(rx);
            lst=q;
            ans^=q;
        }
        else if(op==4)
        {
            q=Splay_GetVal(rx);
            lst=q;
            ans^=q;
        }
        else if(op==5)
        {
            q=Splay[Splay_GetPre(rx)].data;
            lst=q;
            ans^=q;
        }
        else if(op==6)
        {
            q=Splay[Splay_GetSuc(rx)].data;
            lst=q;
            ans^=q;
        }
    }
    cout<<ans;
    return 0;
}
/*
  namespace io: 
  There are two fuctions in it.
  iread: Get the number from running.
  write: Print the number on running.

  SplayNode:
  data: The val of this node.
  fa: The father of this node.
  cnt: How much data does this node have.
  son[2]: The sons of this node.
  size: The size of this tree.

  Splay_Pushup(x):
  Update Splay[x].size .

  Splay_Rotate(x):
  Rotate this node.

  Splay_Splay(x,k):
  Rotate node x under node k.
  Tips: Straight turn on middle, else turn on the bottom.

  Splay_Find(v):
  Find v(*) and let it go to root.
 *: Maybe find the pre of v or the suc of v.

  Splay_GetPre(v) & Splay_GetSuc(v):
  Find the pre of v or the suc of v.

  Splay_Delete(v):
  Delete v in the splay tree.

  Splay_Insert(v):
  Insert v to the splay tree.

  Splay_GetRank(v):
  Get the rank by val in the splay tree.

  Splay_GetVal(k):
  Get the val by rank in the splay tree.

  Splay_Create():
  Create a splay tree.
 */