Treap求调

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <ctime>

using namespace std;
#define ll long long

inline int read()
{
    int x = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x;
}

const int N = 2e6+5,inf = 0x3f3f3f3f;

int ch[N][2],val[N],pri[N],cnt,num[N],root,siz[N];

int New(int v)
{
    val[++cnt] = v;
    pri[cnt] = rand();
    num[cnt] = siz[cnt] = 1;
    ch[cnt][0] = ch[cnt][1] = 0;
    return cnt;
}

void update(int &p)
{
    siz[p] = siz[ch[p][0]]+siz[ch[p][1]]+num[p];
}

void rotate(int &p,bool c)
{
    int q = ch[p][c];
    ch[p][c] = ch[q][c^1];
    ch[q][c^1] = p;
    siz[q] = siz[p];
    update(p);
    p = q;
}

void Insert(int &p,int v)
{
    if(!p)
    {
        p = New(v);
        return ;
    }
    siz[p]++;
    if(v == val[p]){
        num[p]++;return ;
    }
    int c = v>val[p];
    Insert(ch[p][c],v);
    if(pri[p] < pri[ch[p][c]]) rotate(p,c);
}

void Delete(int &p,int v)
{
    if(!p) return ;
    siz[p]--;
    if(v == val[p])
    {
        num[p]--;
        if(num[p]) return ;
        if(!ch[p][0] || !ch[p][1])
            p = ch[p][0]+ch[p][1];
        else
        {
            int c = (pri[ch[p][0]] > pri[ch[p][1]]);
            rotate(p,c^1);
            Delete(ch[p][c],v);
        }
        return ;
    }
    int c = (v > val[p]);
    Delete(ch[p][c],v);
}

int getpre(int v)
{
    int p = root,res = -1;
    while(p)
    {
        if(val[p] < v) res = val[p],p = ch[p][1];
        else p = ch[p][0];
    }
    return res;
}

int getnxt(int v)
{
    int p = root,res = -1;
    while(p)
    {
        if(val[p] > v) res = val[p],p = ch[p][0];
        else p = ch[p][1];
    }
    return res;
}

int Rank(int x,int v)
{
    int res = 0;
    while(x)
    {
        if(v == val[x]) return res + siz[ch[x][0]] + 1;
        else if(v < val[x]) x = ch[x][0];
        else res += siz[ch[x][0]] + num[x],x = ch[x][1];
    }
    return res+1;
}

int getkth(int now,int x)
{
    while(x > 0 && now)
    {
        int t = siz[ch[now][0]];
        if(x <= t) now = ch[now][0];
        else if(x <= t+num[now]) return val[now];
        else x -= (t+num[now]),now = ch[now][1];
    }
    return 0;
}

int main()
{
    int n = read(),m = read();
    srand(time(0));
    for(int i = 1;i <= n;i++)
    {
        int x = read();
        Insert(root,x);
    }
    int last = 0,ans = 0;
    int opt,x;
    for(int i = 1;i <= m;i++)
    {
        opt = read(),x = read()^last;
        if(opt == 1) Insert(root,x);
        else if(opt == 2) Delete(root,x);
        else if(opt == 3) last = Rank(root,x),ans ^= last;
        else if(opt == 4) last = getkth(root,x),ans ^= last;
        else if(opt == 5) last = getpre(x),ans ^= last;
        else if(opt == 6) last = getnxt(x),ans ^= last;
    }
    printf("%d\n",ans);
    return 0;
}