Treap 48pts求调

rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int son[2],size,val,dat,cnt;
}a[2000005];
int cnt,rt;
const int inf=1e9;
int point(int va)
{
    a[++cnt].val=va;
    a[cnt].dat=rand();
    a[cnt].size=1;
    a[cnt].cnt=1;
    return cnt;
}
void push_up(int now)
{
    a[now].size=a[a[now].son[0]].size+a[a[now].son[1]].size+a[now].cnt;
}
void build()
{
    rt=point(-inf),
    a[rt].son[1]=point(inf);
    push_up(rt);
}
void rotate(int &now,int flag)
{
    int tmp=a[now].son[flag^1];
    a[now].son[flag^1]=a[tmp].son[flag];
    a[tmp].son[flag]=now; 
    now=tmp;
    push_up(a[now].son[flag]);
    push_up(now);   

}
void insert(int &now,int va)
{
    if(!now)
    {
        now=point(va);
        return;
    }
    if(va==a[now].val) a[now].cnt++;
    else{
        bool tmp;
        if(va<a[now].val) tmp=0;
        else tmp=1;
        insert(a[now].son[tmp],va);
        if(a[now].dat<a[a[now].son[tmp]].dat) 
        {
            rotate(now,tmp^1);
        }
    }
    push_up(now);
}
void _remove(int &now,int va)
{
    if(!now) return;
    if(va==a[now].val)
    {
        if(a[now].cnt>1)
        {
            a[now].cnt--;
            push_up(now);
            return;
        }
        if(a[now].son[0]||a[now].son[1])
        {
            if(!a[now].son[1]||a[a[now].son[0]].dat>a[a[now].son[1]].dat)
            {
                rotate(now,1);
                _remove(a[now].son[1],va);
            }
            else 
            {
                rotate(now,0);
                _remove(a[now].son[0],va);
            }
            push_up(now);
        }
        else now=0;
        return;
    }
    if(va<a[now].val)
    {
        _remove(a[now].son[0],va);
    }
    else _remove(a[now].son[1],va);
    push_up(now); 
}
int get_rank(int now,int va)
{
    if(!now) return 1;
    if(va==a[now].val) 
    {
        return a[a[now].son[0]].size+1;
    }
    else if(va<a[now].val)
    {
        return get_rank(a[now].son[0],va);
    }
    else return a[a[now].son[0]].size+a[now].cnt+get_rank(a[now].son[1],va);
}
int get_val(int now,int num)
{
    if(!now) return inf;
    if(num<=a[a[now].son[0]].size) return get_val(a[now].son[0],num);
    else if(num<=a[a[now].son[0]].size+a[now].cnt)
    {
        return a[now].val;
    } 
    else return get_val(a[now].son[1],num-a[a[now].son[0]].size-a[now].cnt);
}
int get_pre(int va)
{
    int now=rt;
    int tmp;
    while(now)
    {
        if(a[now].val<va)
        {
            tmp=a[now].val;
            now=a[now].son[1];
        }
        else now=a[now].son[0];
    }
    return tmp;
}
int get_next(int va)
{
    int now=rt;
    int tmp;
    while(now)
    {
        if(a[now].val>va)
        {
            tmp=a[now].val;
            now=a[now].son[0];
        }
        else now=a[now].son[1];
    }
    return tmp;
}
signed main()
{
    srand(time(0));
    build();
    int q,ans=0,n,tmp=0,sum=0;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%lld",&a);
        insert(rt,a);
    }
    int last=0;
    while(q--)
    {
        int op,x;
        scanf("%lld%lld",&op,&x);
        x=x^last;
        if(op==1) insert(rt,x);
        else if(op==2) _remove(rt,x);
        else if(op==3) last=(get_rank(rt,x)),ans^=last,sum+=ans;
        else if(op==4) last=get_val(rt,x+1),ans^=last,sum+=ans;
        else if(op==5) last=get_pre(x),ans^=last,sum+=ans;
        else last=get_next(x),ans^=last,sum+=ans;
    }
    printf("%lld",ans);
    return 0;
}