FHQ 56pts求调 悬3关

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#define int long long
#define N 3000005
using namespace std;
class FHQTreap{
public:
	int root=0,idx=0;
protected:
	struct node{
		int l,r,val,rnd,size;
	}tr[N];
	inline void newnode(int &x,int v){
		x=++idx;
		tr[x].val=v;
		tr[x].rnd=rand();
		tr[x].size=1;
		return ;
	}
	inline void pushup(int p){
		tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;
		return ;
	}
	void split(int p,int v,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		if(tr[p].val<=v){
			x=p;
			split(tr[x].r,v,tr[x].r,y);
			pushup(x);
			return ;
		}else{
			y=p;
			split(tr[y].l,v,x,tr[y].l);
			pushup(y);
			return ;
		}
		return ;
	}
	int merge(int x,int y){
		if(!x||!y){
			return x+y;
		}
		if(tr[x].rnd<tr[y].rnd){
			tr[x].r=merge(tr[x].r,y);
			pushup(x);
			return x;
		}else{
			tr[y].l=merge(x,tr[y].l);
			pushup(y);
			return y;
		}
		return 0;
	}
public:
	inline void insert(int v){
		int x,y,z;
		split(root,v,x,y);
		newnode(z,v);
		root=merge(merge(x,z),y);
		return ;
	}
	inline void del(int v){
		int x,y,z;
		split(root,v,x,z);
		split(x,v-1,x,y);
		y=merge(tr[y].l,tr[y].r);
		root=merge(merge(x,y),z);
		return ;
	}
	inline int getrank(int v){
		int x,y;
		split(root,v-1,x,y);
		int ans=tr[x].size+1;
		root=merge(x,y);
		return ans;
	}
	int getval(int v){
		int p=root;
		while(p){
			if(tr[tr[p].l].size+1==v){
				return tr[p].val;
			}else if(tr[tr[p].l].size>=v) {
				p=tr[p].l;
			}else{
				v-=tr[tr[p].l].size+1;
				p=tr[p].r;
			}
		}
		return 0;
	}
	inline int getpre(int v){
		int x,y,ans;
		split(root,v-1,x,y);
		ans=getval(tr[x].size);
		root=merge(x,y);
		return ans;
	}
	inline int getnxt(int v){
		int x,y,ans;
		split(root,v,x,y);
		ans=getval(1);
		root=merge(x,y);
		return ans;
	}
};
int n,m;
int op,xp;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	FHQTreap fhq;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		fhq.insert(x);
	}
	int last=0,ans=0;
	while(m--){
		cin>>op>>xp;
		int x=xp^last;
		int res=0;
		switch(op){
		case 1:
			fhq.insert(x);
			break;
		case 2:
			fhq.del(x);
			break;
		case 3:
			res=fhq.getrank(x);
			last=res;
			ans^=res;
			break;
		case 4:
			res=fhq.getval(x);
			last=res;
			ans^=res;
			break;
		case 5:
			res=fhq.getpre(x);
			last=res;
			ans^=res;
			break;
		default:
			res=fhq.getnxt(x);
			last=res;
			ans^=res;
			break;
		}
	}
	cout<<ans<<'\n';
	return 0;
}//FHQ 56pts求调 悬4关