P6136 【模板】普通平衡树（数据加强版）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ll int 
const int MAXN=1e6+10,INTMIN=-1e18,INTMAX=1e18;
template<typename T>inline void readT(T &x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
struct Splay{
	int fa[MAXN],sz[MAXN],ch[MAXN][2],cnt,root;
	ll key[MAXN];
	Splay(){
		root=newnode(INTMIN);
		link(root,newnode(INTMAX),1);
	}
	inline int newnode(ll k){
		++cnt;
		key[cnt]=k;
		sz[cnt]=1;
		return cnt;
	}
	inline void update(int x){
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
	}
	//y成为x的w方向儿子 
	inline void link(int x,int y,int w){
		ch[x][w]=y;
		if(y)fa[y]=x;
	}
	inline int getlr(int x,int y){
		return ch[x][1]==y;
	}
	inline void rot(int x,int w){//node x,w 0/1 left/right rotate 
		int z=fa[x],s=ch[x][w^1];
		link(x,ch[s][w],w^1); 
		link(s,x,w);
		if(z)link(z,s,getlr(z,x));
		else fa[s]=0,root=s;
		update(x);
	}
	void splay(int x,int tar){//x splay to target below 
		while(1){//双旋存在 
		if(fa[x]==tar||fa[fa[x]]==tar)break;
		int fw=getlr(fa[x],x),gw=getlr(fa[fa[x]],fa[x]);//father grandfather
		fw==gw?(rot(fa[fa[x]],gw^1),rot(fa[x],fw^1))
			:(rot(fa[x],fw^1),rot(fa[x],gw^1));//in the right 爷爷 已经转下来了
		}
		if(fa[x]!=tar)rot(fa[x],getlr(fa[x],x)^1);
		update(x);
	}
	void insert(ll v){
		int p=root,q;//q上一个节点 
		while(p){
			q=p;
			p=ch[p][v>key[p]]; 
		}
		int x=newnode(v);
		link(q,x,v>key[q]);
		update(q);
		splay(x,0);
	}
	void erase(ll v){
		int p=find(v);
		if(!p)return ;
		int x=ch[p][0],y=ch[p][1];
		while(ch[x][1])x=ch[x][1];
		splay(x,0);
		while(ch[y][0])y=ch[y][0];
		splay(y,x);
		ch[y][0]=0;//cut link 
		update(y);
		update(x);
	}
	int find(ll v){
		int p=root;
		while(p&&key[p]!=v)
			p=ch[p][v>key[p]];
		splay(p,0);
		return p;
	}
	int rank(ll v){
		int ans=0,q,p=root;
		while(p){
			q=p;
			if(key[p]<v)ans+=sz[ch[p][0]]+1,p=ch[p][1];
			else p=ch[p][0];
		}
		splay(q,0);
		return ans;
	}
	ll kth_element(int k){
		k++;
		int p=root;
		while(p){
			if(sz[ch[p][0]]>=k)p=ch[p][0];
			else{
				k-=sz[ch[p][0]]+1;
				if(k==0)break;
				p=ch[p][1];
			}
		}
		splay(p,0);
		return key[p];
	}
	ll prev(ll v){
		ll ans,q,p=root;
		while(p){
			q=p;
			if(key[p]<v)ans=key[p],p=ch[p][1];
			else p=ch[p][0];
		}
		splay(q,0);
		return ans;
	}
	ll succ(ll v){
		ll ans,q,p=root;
		while(p){
			q=p;
			if(key[p]>v)ans=key[p],p=ch[p][0];
			else p=ch[p][1];
		}
		splay(q,0);
		return ans;	
	}
//	inline void debug(int x){
//		if(!x)return ;
//		debug(ch[x][0]);
//		cout<<key[x]<<" ";
//		if(key[x]==INT32_MIN) cout<<"\n";
//		debug(ch[x][1]);
//	}
}splay;
 
int main(){
	int n,m;
	ll l=0,x,ans=0;
	readT(n),readT(m); 
	for(register int i=1;i<=n;++i)readT(x),splay.insert(x);
	while(m--){
		ll op,v;
		readT(op),readT(v);
		if(op==1)v^=l,splay.insert(v);
		else if(op==2)v^=l,splay.erase(v);
		else if(op==3)v^=l,l=splay.rank(v),ans^=l;
		else if(op==4)v^=l,l=splay.kth_element(v),ans^=l;
		else if(op==5)v^=l,l=splay.prev(v),ans^=l;
		else v^=l,l=splay.succ(v),ans^=l;
		//splay.debug(splay.root);
	}
	cout<<ans;
}