有旋treap求调，原版能过QwQ

样例输出5，交上去有20分，吐了

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int S = 1e6+5;
struct treap
{
    int l,r;
    int val,dat;
    int cnt,size;
}a[S];
int tot,root,last,n,m,tmp,ans;
inline int New(int val)
{
    a[++tot].val = val;
    a[tot].dat = rand();
    a[tot].cnt = a[tot].size = 1;
    return tot; 
}
inline void Update(int p){a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;}
inline int Get1(int p,int val)
{
    if(!p) return 0;
    if(val == a[p].val) return a[a[p].l].size + 1;
    if(val < a[p].val) return Get1(a[p].l,val);
    return Get1(a[p].r,val) + a[a[p].l].size + a[p].cnt;    
}
inline int Get2(int p,int rank)
{
    if(!p) return INF;
    if(a[a[p].l].size >= rank) return Get2(a[p].l,rank);
    if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
    return Get2(a[p].r,rank - a[a[p].l].size - a[p].cnt);   
}
inline void zig(int &p)
{
    int q = a[p].l;
    a[p].l = a[q].r,a[q].r = p,p = q;
    Update(a[p].r),Update(p);
}
inline void zag(int &p)
{
    int q = a[p].r;
    a[p].r = a[q].l,a[q].l = p,p = q;
    Update(a[p].l),Update(p);
}
inline void Insert(int &p,int val)
{
    if(!p)
    {
        p = New(val);
        return;     
    }   
    if(val == a[p].val)
    {
        a[p].cnt++,Update(p);
        return;
    }
    if(val < a[p].val)
    {
        Insert(a[p].l,val);
        if(a[p].dat < a[a[p].l].dat) zig(p);
    }
    else
    {
        Insert(a[p].r,val);
        if(a[p].dat < a[a[p].r].dat) zag(p);        
    }
    Update(p);  
}
inline int Getpre(int val)
{
    int ans = 1,p = root;
    while(p)
    {
        if(val == a[p].val)
        {
            if(a[p].l > 0)
            {
                p = a[p].l;
                while(a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        p = val<a[p].val?a[p].l:a[p].r;
    }
    return a[ans].val;
}
inline int Getnext(int val)
{
    int ans = 2,p = root;
    while(p)
    {
        if(val == a[p].val)
        {
            if(a[p].r > 0)
            {
                p = a[p].r;
                while(a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        if(a[p].val > val && a[p].val < a[ans].val) ans = p;
        p = val<a[p].val?a[p].l:a[p].r;
    }
    return a[ans].val;  
}
inline void Remove(int &p,int val)
{
    if(!p) return;
    if(val == a[p].val)
    {
        if(a[p].cnt > 1)
        {
            --a[p].cnt;
            Update(p);
            return;
        }
        if(a[p].l || a[p].r)
        {
            if(!a[p].r || a[a[p].l].dat > a[a[p].r].dat) zig(p),Remove(a[p].r,val);
            else zag(p),Remove(a[p].l,val);
            Update(p);
        }
        else p = 0;
        return;
    }
    val < a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
    Update(p);  
}
int main(int argc,char *argv[])
{
    New(-INF),New(INF);
    root = 1;a[1].r = 2;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i) 
    {
        scanf("%d",&tmp);
        Insert(root,tmp);
    }
    while(m--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        x ^= last;
        switch(opt)
        {
            case 1:
                Insert(root,x);break;
            case 2:
                Remove(root,x);break;
            case 3:
                last = Get1(root,x)-1;
                ans ^= last;
                break;
            case 4:
                last = Get2(root,x+1);
                ans ^= last;
                break;
            case 5:
                last = Getpre(x);
                ans ^= last;
                break;
            case 6:
                last = Getnext(x);
                ans ^= last;
                break;
        }
    }
    printf("%d\n",ans);
    return 0;
}