Splay板子

救救孩子吧，卡常卡了一下午了

浪费评测资源

不过我发现有些时候不Splay更快？？？

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e+6+100;
const int inf = 0x7f7f7f7f;
int n,m,la,ans;
int f[maxn],ch[maxn][2],val[maxn],cnt[maxn],siz[maxn];
int rt,tot;

int read(){
	int v=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	return v*f;
}
void pushup(int x){
	siz[x] = siz[ch[x][0]]+cnt[x]+siz[ch[x][1]];
}
int get(int x){
	return x==ch[f[x]][1];
}
void connect(int s,int fa,int dir){
	f[s] = fa;
	ch[fa][dir] = s;
}
void rotate(int x){
	int fa=f[x],gfa=f[fa];
	int s1=get(x),s2=get(fa);
	int s=ch[x][s1^1];
	connect(s,fa,s1);
	connect(x,gfa,s2);
	connect(fa,x,s1^1);
	pushup(fa);
	pushup(x); 
}
void Splay(int x,int gol){
	for(int fa;(fa=f[x])&&fa!=gol;rotate(x)){
		if(f[fa]!=gol) rotate(get(x)==get(fa)?fa:x);
	}
	if(!gol) rt = x;
}
void find(int x){
	int cur=rt;
	while(ch[cur][x>val[cur]]&&val[cur]!=x)  cur = ch[cur][x>val[cur]];
	Splay(cur,0);
}
int pre(int x){
	find(x);
	if(val[rt]<x) return rt;
	int cur=ch[rt][0];
	while(ch[cur][1]) cur = ch[cur][1];
	return cur;
}
int suc(int x){
	find(x);
	if(val[rt]>x) return rt;
	int cur=ch[rt][1];
	while(ch[cur][0]) cur = ch[cur][0];
	return cur;
}
int rank(int x){
	int cur=rt,rk=0;
	while(cur){
		if(val[cur]<x){
			rk += siz[ch[cur][0]]+cnt[cur];
			cur=ch[cur][1];
		}
		else if(val[cur]>x){
			cur=ch[cur][0];
		}
		else if(val[cur]==x){
			rk+=siz[ch[cur][0]];
			break;
		}
	}
	//Splay(cur,0);
	//if(cur) ++rk; 
	return rk;
}
int kth(int k){
	int cur=rt;
	while(true){
		if(k<=siz[ch[cur][0]]) cur=ch[cur][0];
		else if(k>siz[ch[cur][0]]+cnt[cur]) k-=siz[ch[cur][0]]+cnt[cur],cur=ch[cur][1];
		else{
			//Splay(cur,0);
			return cur;
		}
	}
}
void ins(int x){
	int cur=rt,fa=0;
	while(cur&&val[cur]!=x){
		fa=cur;
		cur=ch[cur][x>val[cur]]; 
	}
	if(cur){
		++cnt[cur];
	}
	else{
		cur= ++tot;
		val[cur] = x;
		siz[cur] = cnt[cur] = 1;
		f[cur] = fa;
		if(fa) ch[fa][x>val[fa]] = cur;
	}
	Splay(cur,0);
}
void del(int x){
	int lst=pre(x),nxt=suc(x);
	Splay(lst,0);
	Splay(nxt,lst);
	int cur = ch[nxt][0];
	if(cnt[cur]>1){
		--cnt[cur];
		Splay(cur,0);
	}else{
		ch[nxt][0]=0;
		f[cur]=siz[cur]=cnt[cur]=ch[cur][0]=ch[cur][1]=0;
		pushup(nxt);
		pushup(lst);
	}
}
int main(){
	//freopen("61361.in","r",stdin);
	//freopen("ddd.out","w",stdout);
	n=read();m=read();
	ins(inf);ins(-inf);
	for(register int i=1;i<=n;++i){
		int x = read();
		ins(x);
	}
	//printf("ccf\n");
	for(register int i=1;i<=m;++i){
		//if(i)printf("ccf %d %d\n",i,la);
		int opt=read(),x=read()^la;
		if(opt==1) ins(x);
		if(opt==2) del(x);
		if(opt<=2) continue;
		if(opt==3) la=rank(x);
		if(opt==4) la=val[kth(x+1)];
		if(opt==5) la=val[pre(x)];
		if(opt==6) la=val[suc(x)];
		ans ^= la;
		//printf("%d\n",la);
	}
	printf("%d\n",ans);
	return 0;
}