splay板子题

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int sum=0,x=1;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘){
		if(ch==‘-‘)
			x=0;
		ch=getchar();
	}
	while(ch>=‘0‘&&ch<=‘9‘)
		sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
	return x?sum:-sum;
}
inline void write(int x){
	if(x<0)
		putchar(‘-‘),x=-x;
	if(x>9)
	 	write(x/10);
	putchar(x%10+‘0‘);
}
const int M=2e5+5;
const int inf=0x3f3f3f3f;
int ch[M][2],val[M],cnt[M],fa[M],sz[M],ncnt,root;
int  ck(int x){
	return ch[fa[x]][1]==x;
}
void up(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
void rotate(int x){
	int y=fa[x];
	int z=fa[y];
	int k=ck(x);
	int w=ch[x][k^1];
	ch[y][k]=w,fa[w]=y;
	ch[z][ck(y)]=x,fa[x]=z;
	ch[x][k^1]=y,fa[y]=x;
	up(y),up(x);
}
void splay(int x,int goal=0){//将x旋转为goal的儿子，如果goal是0则旋转到根
	while(fa[x]!=goal){//一直旋转到x成为goal的儿子
		int y=fa[x],z=fa[y];//父节点祖父节点
		if(z!=goal)//如果Y不是根节点，则分为两类来旋转（如果随意旋转会达不到查询效果） 
			ck(x)^ck(y)?rotate(x):rotate(y);
		rotate(x);//无论怎么样最后的一个操作都是旋转x
	}
	if(!goal)
		root=x;//如果goal是0，则将根节点更新为x
}
void find(int x){//查找x的位置，并将其旋转到根节点 
	if(!root)//树空 
		return ;
	int cur=root;
	while(ch[cur][x>val[cur]]&&x!=val[cur])//当存在儿子并且当前位置的值不等于x 
		cur=ch[cur][x>val[cur]];//跳转到儿子，查找x的父节点
	splay(cur);//把当前位置旋转到根节点
}
void insertt(int x){//插入x
	int cur=root,p=0;//当前位置cur，cur的父节点p 
	while(cur&&val[cur]!=x){//当u存在并且没有移动到当前的值
		p=cur;//向下u的儿子，父节点变为u
		cur=ch[cur][x>val[cur]];//大于当前位置则向右找，否则向左找
	}
	if(cur)//存在这个值的位置
		cnt[cur]++;//增加一个数
	else{//不存在这个数字，要新建一个节点来存放
		cur=++ncnt;//新节点的位置
		if(p)//如果父节点非根
			ch[p][x>val[p]]=cur;//不存在儿子
		fa[cur]=p;//父节点
		ch[cur][0]=ch[cur][1]=0;
		val[cur]=x;//值
		cnt[cur]=sz[cur]=1;//数量，大小 
	}
	splay(cur);//把当前位置移到根，保证结构的平衡。注意前面因为更改了子树大小，所以这里必须Splay上去进行pushup保证size的正确。
}
int kth(int k){
	int u=root;
	while(true){
		if(ch[u][0]&&k<=sz[ch[u][0]])
			u=ch[u][0];
		else if(k>sz[ch[u][0]]+cnt[u])
			k-=sz[ch[u][0]]+cnt[u],u=ch[u][1];
		else
			return u;	
	}
}
int  pre(int x){//查找x的前驱(0)或者后继(1)
	find(x);
	if(val[root]<x)//如果当前节点的值小于x并且要查找的是前驱
		return root;
	int u=ch[root][0];//前驱再左儿子上找 
	while(ch[u][1])
		u=ch[u][1];
	return u;//返回位置 
}
int succ(int x){
	find(x);
	if(val[root]>x)//如果当前节点的值大于x并且要查找的是后继
		return root;
	int u=ch[root][1];//后继在右儿子上找 
	while(ch[u][0])
		u=ch[u][0];
	return u;
}
void remove(int x){
	int las=pre(x),nex=succ(x);
	splay(las,0),splay(nex,las);
	//将前驱旋转到根节点，后继旋转到根节点下面
    //很明显，此时后继是前驱的右儿子，x是后继的左儿子，并且x是叶子节点
	int del=ch[nex][0];//后继的左儿子
	if(cnt[del]>1)//如果超过一个
		cnt[del]--,splay(del,0);//直接减少一个
	else
		ch[nex][0]=0;//这个节点直接丢掉（不存在了）
}
void init(){
	memset(ch,0,sizeof(cnt));
	memset(cnt,0,sizeof(cnt));
	memset(sz,0,sizeof(sz));
	memset(val,0,sizeof(val));
	memset(fa,0,sizeof(fa));
	ncnt=root=0;
}
int main(){
	
	
	int n;
	while(~scanf("%d",&n)){
		init();
		insertt(inf);
		insertt(-inf);
		while(n--){
			
			int op=read(),x=read();
			if(op==1)
				insertt(x);
			else if(op==2)
				remove(x);
			else if(op==3)
				find(x),write(sz[ch[root][0]]),putchar(‘\n‘);
			else if(op==4)
				write(val[kth(x+1)]),putchar(‘\n‘);
			else if(op==5)
				write(val[pre(x)]),putchar(‘\n‘);
			else
				write(val[succ(x)]),putchar(‘\n‘);
		}
		putchar(‘\n‘);
	}
	return 0;
}