splay 8分求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
	x=0;bool f=0;char ch;
	while(!isdigit(ch=getchar()))f|=ch=='-';
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	x=f?-x:x;
}
const int N=5e5+5;
class SplayTree{
	public:
		int root;
	private:
		int tot;
		int son[N],ch[N][2],cnt[N],fa[N],val[N];
		inline void update(int x){
			son[x]=son[ch[x][0]]+son[ch[x][1]]+cnt[x];
		}
		inline void rotate(int x){
			int f=fa[x],g=fa[f];
			bool k=ch[f][1]==x,K=ch[g][1]==f;
			ch[g][K]=x;
			fa[x]=g;
			ch[f][k]=ch[x][k^1];
			fa[ch[x][k^1]]=f;
			fa[f]=x;
			ch[x][k^1]=f;
			update(f);update(x);
		}
		inline void splay(int x){
//			while(fa[x]){
//				int f=fa[x],g=fa[f];
//				if(g&&((ch[g][0]^f)==(ch[f][0]^x)))rotate(f);
//				rotate(x);
//			}
//			root=x;
			while(fa[x])rotate(x);
			root=x;
		}
	public:
		inline void retree(){
			tot=root=0;
			for(int i=0;i<N;i++)son[i]=ch[i][0]=ch[i][1]=cnt[i]=fa[i]=val[i]=0;
		}
		inline void dfs(int u){
			if(!u)return;
			dfs(ch[u][0]);
			printf("val:%d cnt:%d fa:%d ch:%d %d\n",val[u],cnt[u],val[fa[u]],val[ch[u][0]],val[ch[u][1]]);
			dfs(ch[u][1]);
		}
		inline void insert(int x){
			if(!tot){val[++tot]=x,cnt[tot]=son[tot]=1,root=tot;return ;}
			int u=root;
			while(ch[u][x>val[u]]&&(val[u]^x))++son[u],u=ch[u][x>val[u]];
			if(x==val[u])++cnt[u],splay(u);
			else{
				val[++tot]=x;
				son[tot]=cnt[tot]=1;
				fa[tot]=u,ch[u][x>val[u]]=tot;
				splay(tot);
			}
		}
		inline int find(int x){
			int ans=1,u=root;
			while(ch[u][x>val[u]]&&(val[u]^x)){
				if(x>val[u])ans+=son[ch[u][0]]+cnt[u];
				u=ch[u][x>val[u]];
			}
			if(x>val[u])ans+=cnt[u];
			splay(u);
			return ans;
		}
		inline int kth(int x){
			int u=root;
			if(x>son[u])return -1;
			while(ch[u][x>=son[ch[u][0]]+cnt[u]]&&x){
				if(x>=son[ch[u][0]]+cnt[u])x-=son[ch[u][0]]+cnt[u],u=ch[u][1];
				else u=ch[u][0];
			}
			if(!x)u=fa[u];
			splay(u);
			return val[u];
		}
		inline int bound(int x,bool k){//0->qq,1->hj
			find(x);
			int u=root;
			if((val[u]>x&&k==1)||(val[u]<x&&k==0))return val[u];
			if(!ch[u][k]) return -1;
			u=ch[u][k];
			while(ch[u][k^1]) u=ch[u][k^1];
			splay(u);
			return val[u];
		}
		inline void remove(int x){
			int nxt=bound(x,0),last=bound(x,1);
			splay(last);
			splay(nxt);
			int u=ch[last][0];
			if(!u) return;
			--son[nxt],--son[last];
			if(cnt[u]==1)ch[last][0]=0;
			else --cnt[u],--son[u],splay(u);
		}
};
SplayTree t;
signed main(){
	t.retree();t.insert(-0x7fffffff),t.insert(0x7fffffff);
	int n;
	read(n);
	int op, x;
	while(n--){
		read(op),read(x);
		if(op == 1) t.insert(x);
		else if(op == 2) t.remove(x);
		else if(op == 3) printf("%d\n",t.find(x+1));
		else if(op == 4) printf("%d\n",t.kth(x+1));
		else if(op == 5) printf("%d\n",t.bound(x,0));
		else printf("%d\n",t.bound(x,1));
	}
	return 0;
}