MnZn刚学一秒splay,44分求调

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1.5e6+5,INF=0x3f3f3f3f;
const ll mod=1e9+7;
int read()
{
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=x*10+c-48;c=getchar();}
    return f*x;
}
int n,idx,root,m;
struct Splay
{
    int s[2],v,p,size;
    int cnt;
    void init(int _v,int _p)
    {
        v=_v,p=_p;
        size=cnt=1;
    }
}tr[N];

void push_up(int x)
{
    tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    push_up(y),push_up(x);
}

void splay(int x,int k)
{
    while(tr[x].p!=k)
    {
        int y=tr[x].p,z=tr[y].p;
        if(z!=k)
            if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root=x;
}

void find(int v)
{
    int x=root;
    while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
        x=tr[x].s[v>tr[x].v];
    splay(x,0);
}

int get_prev(int v)
{
    find(v);
    int x=root;
    if(tr[x].v<v) return x;
    x=tr[x].s[0];
    while(tr[x].s[1]) 
        x=tr[x].s[1];
    splay(x,0);
    return x;
}

int get_next(int v)
{
    find(v);
    int x=root;
    if(tr[x].v>v) return x;
    x=tr[x].s[1];
    while(tr[x].s[0]) 
        x=tr[x].s[0];
    splay(x,0);
    return x;
}

void del(int v)
{
    int prev=get_prev(v),next=get_next(v);
    splay(prev,0),splay(next,prev);
    int son=tr[next].s[0];
    if(tr[son].cnt>1)
        tr[son].cnt--,splay(son,0);
    else
        tr[next].s[0]=0,splay(next,0);
}

int get_kth(int k)
{
    int u=root;
    while(u)
    {
        if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
        else if(tr[tr[u].s[0]].size+tr[u].cnt>=k)
        {
            splay(u,0);
            return tr[u].v;
        } 
        else k-=tr[tr[u].s[0]].size+tr[u].cnt,u=tr[u].s[1];
    }
    return -1;
}

void insert(int v)
{
    int u=root,p=0;
    while(u)
    {
        if(tr[u].v==v)
        {
            splay(u,0);
            tr[u].cnt++;
            return;
        }
        p=u;
        u=tr[u].s[v>tr[u].v];
    }
    u=++idx;
    if(p) tr[p].s[v>tr[p].v]=u;
    tr[u].init(v,p);
    splay(u,0);
}

signed main()              //主函数
{
    n=read(),m=read();
    int last=0,res=0;
    for(int i=1;i<=n;i++)
    {
        int v=read();
        insert(v);
    }
    insert(-INF),insert(INF);
    while(m--)
    {
        int op=read(),x=read();
        x^=last;
        if(op==1)
        {
            insert(x);
        }
        else if(op==2)
        {
            del(x);
        }
        else if(op==3)
        {
            insert(x);
            find(x);
            last=tr[tr[root].s[0]].size;
            //cout<<last<<endl;
            res^=last;
            del(x);
        }
        else if(op==4)
        {
            last=get_kth(x+1);
            //cout<<last<<endl;
            res^=last;
        }
        else if(op==5)
        {
            insert(x);
            last=tr[get_prev(x)].v;
            //cout<<last<<endl;
            res^=last;
            del(x);
        }
        else if(op==6)
        {
            insert(x);
            last=tr[get_next(x)].v;
            //cout<<last<<endl;
            res^=last;
            del(x);
        }
    }
    printf("%lld\n", res);
    return 0;
}