rt

评测记录

/* 2024-12-15-19:20 by _dbq_ */
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<stdlib.h>
#include<vector>
#define LL long long
#define ULL unsigned long long
#define cint const int 
using namespace std;
cint INTINF=0x7f7f7f7f;
const LL LLINF=9e18;
cint N=2e6+10;
int f[N],son[N][2],val[N],cnt[N];
int siz[N];
int root,tot;
int last=0;
int ans=0;
inline LL read(){
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(LL x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return ;
}
bool which_son(int x){
    return x==son[f[x]][1];
}
int new_node(int x,int fa){
    tot++;
    son[tot][0]=son[tot][1]=0;
    f[tot]=fa;
    siz[tot]=cnt[tot]=1;
    val[tot]=x;
    return tot;
}
void update(int x){
    if(x){
        siz[x]=cnt[x];
        if(son[x][0])
            siz[x]+=siz[son[x][0]];
        if(son[x][1])
            siz[x]+=siz[son[x][1]];
    }
    return ;
}
void rotate(int x){
    int fa=f[x],grfa=f[fa],d=which_son(x);
    if(grfa)
        son[grfa][which_son(fa)]=x;
    f[x]=grfa;
    son[fa][d]=son[x][d^1];
    f[son[x][d^1]]=fa;
    son[x][d^1]=fa;
    f[fa]=x;
    update(fa);
    update(x);
    return ;
}
void splay(int x,int y){
    if(x==y) return ;
    while(f[x]!=y){
        int fa=f[x],grfa=f[fa];
        if(grfa!=y)
            rotate(which_son(x)==which_son(fa)?fa:x);
        rotate(x);
    }
    if(y==0){
        root=x;
    }
    return ;
}
void insert(int x){
    if(root==0)
    {
        int idx=new_node(x,0);
        root=idx;
        return ;
    }
    int now=root,fa=0;
    while(1){
        if(x==val[now]){
            cnt[now]++;
            update(now);
            update(fa);
            splay(now,0);
            break;
        }
        fa=now,now=son[now][val[now]<x];
        if(now==0){
            int idx=new_node(x,fa);
            son[fa][val[fa]<x]=idx;
            update(fa);
            splay(idx,0);
            break;
        }
    }
    return ;    
}
int get_num(int rnk){
    int now=root,res;
    while(1){
        if(son[now][0]&&rnk<=siz[son[now][0]])
            now=son[now][0];
        else {
            int num=(son[now][0]?siz[son[now][0]]:0)+cnt[now];
            if(num>=rnk){
                res=val[now];
                break;
            }
            rnk-=num;
            now=son[now][1];
        }
    }
    splay(now,0);
    return res;
}
int get_rnk(int x){
    int now=root,res=0,fa=0;
    while(now){
        if(val[now]<x){
            res+=siz[son[now][0]]+cnt[now];
            fa=now,now=son[now][1];
        }
        else{
            fa=now,now=son[now][0];
        }
    }
    splay(fa,0);
    return res;
}
int get_pre(int x){
    int now=root,res=0;
    while(now){
        if(val[now]>=x)
            now=son[now][0];
        else
            res=now,now=son[now][1];
    }
    return res;
}
int get_suc(int x){
    int now=root,res=0;
    while(now){
        if(val[now]<=x)
            now=son[now][1];
        else
            res=now,now=son[now][0];
    }
    return res;
}
void del(int x){
    int pre=get_pre(x),suc=get_suc(x);
    splay(pre,0),splay(suc,root);
    int rson=son[root][1],rsls=son[rson][0];
    if(cnt[rsls]>1)
        cnt[rsls]--,siz[rsls]--;
    else
        cnt[rsls]--,siz[rsls]--,son[rson][0]=0;
    
    update(rson);
    update(root);
    return ;
}
void solve()
{
    int op=read(),x=read();
    x=last^x;
    if(op==1)
        insert(x);
    if(op==2)
        del(x);
    if(op==3)
        last=get_rnk(x);
    if(op==4)
        last=get_num(x+1);
    if(op==5)
        last=val[get_pre(x)];
    if(op==6)
        last=val[get_suc(x)];
    if(op==3||op==4||op==5||op==6)
        ans=last^ans;
}
int main()
{
    #ifdef dbq
    freopen("P6136(splay).in","r",stdin);
    freopen("P6136(splay).out","w",stdout);
    #endif
    int n=read(),T=read();
    insert(INTINF),insert(-INTINF);
    while(n--){
        insert(read());
    }
    while(T--){
        solve();
    }
    cout<<ans;
    return 0;
}