Splay50pts,求助

rt

参考的代码

蒟蒻的提交记录

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,q=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')q=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return q*x;
}
struct Splay
{
    int siz,num,fa,cnt;
    int son[2];
}t[2000001];
int n,m,last,root,tot,ans;
const int inf=2147483647;
inline void maintain(int x)
{
    t[x].siz=t[t[x].son[0]].siz+t[t[x].son[1]].siz+t[x].cnt;
}
inline void rotate(int x)
{
    int y=t[x].fa,z=t[y].fa;
    int w=(t[y].son[1]==x);
    t[z].son[t[z].son[1]==y]=x;
    t[x].fa=z;
    t[y].son[w]=t[x].son[w^1];
    t[t[y].son[w]].fa=y;
    t[x].son[w^1]=y;
    t[y].fa=x;
    maintain(y);
    maintain(x);
}
inline void splay(int x,int to)
{
    while(t[x].fa!=to)
    {
        int y=t[x].fa,z=t[y].fa;
        if(z!=to)
        {
            if((x==t[y].son[0])^(y==t[z].son[0]))
            rotate(x);
            else
            rotate(y);
        }
        rotate(x);
    }
    if(to==0)
    root=x;
}
inline void find(int x)
{
    int p=root;
    if(!p)return;
    while(t[p].son[x>t[p].num]&&x!=t[p].num)
    p=t[p].son[x>t[p].num];
    splay(p,0);
}
inline void insert(int x)
{
    int p=root,ff=0;
    while(p&&t[p].num!=x)
    {
        ff=p;
        p=t[p].son[x>t[p].num];
    }
    if(p)t[p].cnt++;
    else
    {
        p=++tot;
        if(ff)
        t[ff].son[x>t[ff].num]=p;
        t[p].fa=ff;
        t[p].son[0]=t[p].son[1]=0;
        t[p].siz=1;
        t[p].num=x;
        t[p].cnt=1;
    }
    splay(p,0);
}
inline int rk(int x)
{
    find(x);
    if(t[root].num<x)
    return t[t[root].son[0]].siz+1;
    else
    return t[t[root].son[0]].siz;
}
inline int kth(int x)
{
    int p=root;
    if(t[p].siz<x)return 0;
    while(1)
    {
        int y=t[p].son[0];
        if(x>t[y].siz+t[p].cnt)
        {
            x-=(t[y].siz+t[p].cnt);
            p=t[p].son[1];
        }
        else
        {
            if(t[y].siz>=x)
            p=y;
            else
            {
                splay(p,0);
                return t[p].num;
            }
        }
    }
}
inline int nxt(int x,int f)
{
    find(x);
    int p=root;
    if(t[p].num>x&&f)return p;
    if(t[p].num<x&&!f)return p;
    p=t[p].son[f];
    while(t[p].son[f^1])
    p=t[p].son[f^1];
    splay(p,0);
    return p;
}
inline void del(int x)
{
    int y=nxt(x,0);
    int z=nxt(x,1);
    splay(y,0);
    splay(z,y);
    int u=t[z].son[0];
    if(t[u].cnt>1)
    {
        t[u].cnt--;
        splay(u,0);
    }
    else
    {
        t[z].son[0]=0;
        splay(z,0);
    }
}
int main()
{
    n=read();
    m=read();
    insert(inf);
    insert(-inf);
    for(register int i=1;i<=n;i++)
    {
        int an;
        an=read();
        insert(an);
    }
    while(m--)
    {
        int opt,x;
        opt=read();
        x=read();
        x^=last;
        if(opt==1)
        {
            insert(x);
        }
        if(opt==2)
        {
            del(x);
        }
        if(opt==3)
        {
            last=rk(x);
            ans^=last;
        }
        if(opt==4)
        {
            last=kth(x+1);
            ans^=last;
        }
        if(opt==5)
        {
            last=t[nxt(x,0)].num;
            ans^=last;
        }
        if(opt==6)
        {
            last=t[nxt(x,1)].num;
            ans^=last;
        }
    }
    cout<<ans<<endl;
    return 0;
}