有旋treap求调

rt

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int inf=2e9;
int n,m;
int last,an;
int root,idx;
struct Node
{
    int l,r;
    int key,val;
    int cnt,size;
} tr[1145140];

void push_up(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}

int get_node(int key)
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].cnt=tr[idx].size=1;
    return idx;
}

void build()
{
    get_node(-inf);
    get_node(inf);
    root=1;
    tr[1].r=2;
    push_up(root);
}

void zig(int &p)
{
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    push_up(tr[p].r);
    push_up(p);
}

void zag(int &p)
{
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    push_up(tr[p].l);
    push_up(p);
}

void add(int &p,int key)
{
    if(!p) p=get_node(key);
    else if(tr[p].key==key)
      tr[p].cnt++;
    else if(tr[p].key>key)
    {
        add(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)
          zig(p);  
    }  
    else 
    {
        add(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)
          zag(p);
    }
    push_up(p);
}

void de(int &p,int key)
{

    if(!p)  return ;
    if(tr[p].key==key)
    {
        if(tr[p].cnt>1)
          tr[p].cnt--;
        else if(tr[p].l||tr[p].r)
        {
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
            {
                zig(p);
                de(tr[p].r,key);
            }
            else
          {
              zag(p);
              de(tr[p].l,key);
        } 
        }
        else
          p=0;
    }
    else if(tr[p].key>key)
      de(tr[p].l,key);
    else
      de(tr[p].r,key);

    push_up(p);   
}

int get_rank(int p,int key)
{
    if(!p)  
      return 0;
  if(tr[p].key==key)
    return tr[tr[p].l].size;
  if(tr[p].key>key)
    return get_rank(tr[p].l,key);
  return tr[tr[p].l].size+tr[p].cnt+get_rank(tr[p].r,key);   
}

int get_key(int p,int rank)
{
    if(!p) return inf;
    if(tr[tr[p].l].size>=rank)
      return get_key(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].cnt>=rank)
      return tr[p].key;
    return get_key(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);      
}

int get_head(int p,int key)
{
    if(!p)  
      return -inf;
    if(tr[p].key>=key)
      return get_head(tr[p].l,key);
    return max(tr[p].key,get_head(tr[p].r,key));      
}

int get_next(int p,int key)
{
    if(!p)
      return inf;
    if(tr[p].key<=key)
      return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));      
}

signed main()
{
    freopen("P6136_18.in","r",stdin);
    freopen("tiaoshi.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    build();
    cin>>n>>m;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        add(root,x);
    }
    int op,ans=0;
    while(m--)
    {
        ans=0;
        cin>>op>>x;
        x^=last;
        if(op==1) add(root,x);
        if(op==2) de(root,x);
        if(op==3) ans=get_rank(root,x);
        if(op==4) ans=get_key(root,x+1);
        if(op==5) ans=get_head(root,x);
        if(op==6) ans=get_next(root,x);
        if(ans) last=ans;
        an^=ans;
    }
    cout<<an<<"\n";
    return 0;
}