Splay求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int n,root,tot;
int ch[maxn+5][2],fa[maxn+5],val[maxn+5],siz[maxn+5],cnt[maxn+5];
int newnode(int v){
	val[++tot]=v,siz[tot]=cnt[tot]=1;
	return tot;
}
void update(int x){
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
int get(int x){
	return x==ch[fa[x]][1];
}
void clear(int x){
	ch[x][0]=ch[x][1]=fa[x]=val[x]=siz[x]=cnt[x]=0;
}
void rotate(int x){
	int y=fa[x],z=fa[y],d=get(x);
	ch[y][d]=ch[x][d^1];
	if(ch[x][d^1]){
		fa[ch[x][d^1]]=y;
	}
	ch[x][d^1]=y,fa[y]=x,fa[x]=z;
	if(z){
		ch[z][y==ch[z][1]]=x;
	}
	update(y);
	update(x);
}
void splay(int x){
	while(fa[x]){
		int y=fa[x],z=fa[y];
		if(z){
			if(get(x)==get(y)){
				rotate(y);
			}
			else{
				rotate(x);
			}
		}
		rotate(x);
	}
	root=x;
}
void ins(int v){
	if(!root){
		root=newnode(v);
	}
	int x=root,f=0;
	while(1){
		if(val[x]==v){
			cnt[x]++;
			update(x);
			update(f);
			splay(x);
			break;
		}
		f=x,x=ch[x][val[x]<v];
		if(!x){
			x=newnode(v),fa[x]=f,ch[f][val[f]<v]=x;
			update(x);
			update(f);
			splay(x);
			break;
		}
	}
}
int getrnk(int v){
	int ans=0,x=root;
	while(1){
		if(v<val[x]){
			x=ch[x][0];
		}
		else{
			ans+=siz[ch[x][0]];
			if(v==val[x]){
				splay(x);
				return ans+1;
			}
			ans+=cnt[x],x=ch[x][1];
		}
	}
}
int getkth(int k){
	int x=root;
	while(1){
		if(ch[x][0]&&k<=siz[ch[x][0]]){
			x=ch[x][0];
		}
		else{
			k-=cnt[x]+siz[ch[x][0]];
			if(k<=0){
				splay(x);
				return val[x];
			}
			x=ch[x][1];
		}
	}
}
int getpre(){
	int x=ch[root][0];
	if(!x){
		return x;
	}
	while(ch[x][1]){
		x=ch[x][1];
	}
	splay(x);
	return x;
}
int getnext(){
	int x=ch[root][1];
	if(!x){
		return x;
	}
	while(ch[x][0]){
		x=ch[x][0];
	}
	splay(x);
	return x;
}
void del(int v){
	getrnk(v);
	if(cnt[root]>1){
		cnt[root]--;
		update(root);
		return;
	}
	if(!ch[root][0]&&!ch[root][1]){
		clear(root);
		root=0;
	}
	else if(!ch[root][0]){
		int x=root;
		root=ch[root][1],fa[root]=0;
		clear(x);
	}
	else if(!ch[root][1]){
		int x=root;
		root=ch[root][0],fa[root]=0;
		clear(x);
	}
	else{
		int x=root,tmp=getpre();
		fa[ch[x][1]]=tmp,ch[tmp][1]=ch[x][1];
		clear(x);
		update(root);
	}
}
int main(){
	scanf("%d",&n);
	while(n--){
		int op,x;
		scanf("%d %d",&op,&x);
		if(op==1){
			ins(x);
		}
		if(op==2){
			del(x);
		}
		if(op==3){
			ins(x);
			printf("%d\n",getrnk(x));
			del(x);
		}
		if(op==4){
			printf("%d\n",getkth(x));
		}
		if(op==5){
			ins(x);
			printf("%d\n",val[getpre()]);
			del(x);
		}
		if(op==6){
			ins(x);
			printf("%d\n",val[getnext()]);
			del(x);
		}
	}
	return 0;
}