RT

先maintain(fa[x])再maintain(x)居然没卡掉

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+5; 
int n,m;
int op,qwq;
struct Splay{
	int rt,tot,fa[MAXN],sz[MAXN],son[MAXN][2],val[MAXN],cnt[MAXN];
	void pre(){
		rt=tot=0;
		memset(fa,0,sizeof(fa));
		memset(sz,0,sizeof(sz));
		memset(son,0,sizeof(son));
		memset(val,0,sizeof(val));
		memset(cnt,0,sizeof(cnt));
		return;
	}
	void maintain(int x){
		sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
		return;
	}
	bool get(int x){
		return x==son[fa[x]][1];
	}
	void clear(int x){
		fa[x]=sz[x]=son[x][0]=son[x][1]=val[x]=cnt[x]=0;
		return;
	}
	void rotate(int x){
		int Y=fa[x],Z=fa[Y],son_type=get(x);
		son[Y][son_type]=son[x][son_type^1];
		if(son[x][son_type^1])fa[son[x][son_type^1]]=Y;
		son[x][son_type^1]=Y;
		fa[Y]=x;
		fa[x]=Z;
		if(Z)son[Z][Y==son[Z][1]]=x;
		maintain(x),maintain(Y);//这里写反了，但是它居然AC了
		return;
	}
	void splay(int x){
		for(int f=fa[x];f=fa[x],f;rotate(x))if(fa[f])rotate(get(f)==get(x)?f:x);
		rt=x;
		return;
	}
	void insert(int x){
		if(!rt){
			val[++tot]=x;
			cnt[tot]++;
			rt=tot;
			maintain(rt);
			return;
		}
		int now=rt,father=0;
		while(1){
			if(val[now]==x){
				cnt[now]++;
				maintain(now);
				maintain(father);
				splay(now);
				return;
			}
			father=now;
			now=son[now][val[now]<x];
			if(!now){
				val[++tot]=x;
				cnt[tot]++;
				fa[tot]=father;
				son[father][val[father]<x]=tot;
				maintain(tot);
				maintain(father);
				splay(tot);
				return;
			} 
		}
		return;
	}
	int rk(int x){
		int ans=0,now=rt;
		while(1){
			if(!now)return ans+1;
			if(x<val[now])now=son[now][0];
			else{
				ans+=sz[son[now][0]];
				if(val[now]==x){
					splay(now);
					return ans+1;
				}
				ans+=cnt[now];
				now=son[now][1];
			} 
		} 
	}
	int kth(int x){
		int now=rt;
		while(1){
			if(son[now][0]&&x<=sz[son[now][0]])now=son[now][0];
			else{
				x-=sz[son[now][0]]+cnt[now];
				if(x<=0){
					splay(now);
					return val[now];
				}
				now=son[now][1];
			}
		}
	} 
	int lst(){
		int now=son[rt][0];
		if(!now)return now;
		while(son[now][1])now=son[now][1];
		splay(now);
		return now;
	}
	int nxt(){
		int now=son[rt][1];
		if(!now)return now;
		while(son[now][0])now=son[now][0];
		splay(now);
		return now;
	}
	void erase(int x){
		rk(x);
		if(cnt[rt]>1){
			cnt[rt]--;
			maintain(rt);
			return;
		}
		if(!son[rt][0]&&!son[rt][1]){
			clear(rt);
			rt=0;
			return;
		}
		if(!son[rt][0]){
			int now=rt;
			rt=son[now][1];
			fa[rt]=0;
			clear(now);
			return;
		}
		if(!son[rt][1]){
			int now=rt;
			rt=son[now][0];
			fa[rt]=0;
			clear(now);
			return;
		}
		int now=rt,new_x=lst();
		fa[son[now][1]]=new_x;
		son[new_x][1]=son[now][1];
		clear(now);
		maintain(rt);
		return;
	}
}S;
int last,ans;
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	S.pre();
	for(int i=1;i<=n;i++){
		cin>>qwq;
		S.insert(qwq);
	}
	while(m--){
		cin>>op>>qwq;
		qwq^=last;
		switch(op){
			case 1:S.insert(qwq);break;
			case 2:S.erase(qwq);break;
			case 3:last=S.rk(qwq);ans^=last;break;
			case 4:last=S.kth(qwq);ans^=last;break;
			case 5:S.insert(qwq);last=S.val[S.lst()];ans^=last;S.erase(qwq);break;
			case 6:S.insert(qwq);last=S.val[S.nxt()];ans^=last;S.erase(qwq);break;
		} 
	}
	cout<<ans;
	return 0;
}