RT，测样例输出

106465
89851
0

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int Maxn=100000+10;
int v[Maxn],g[Maxn][2];
int c[Maxn],s[Maxn],f[Maxn];
/*
v[x]:点x储存的值
c[x]:x点重复元素的个数
s[x]:以x为根的子树大小
f[x]:x的父亲
*/
int m,idcnt,root;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int id(int x)
{
	return x==g[f[x]][1];
}
inline void con(int x,int y,int k)
{
	if(x)f[x]=y;
	if(y)g[y][k]=x;
}
inline void push_up(int x)
{
	s[x]=s[g[x][0]]+s[g[x][1]]+c[x];
}
void rot(int x)
{
	int y=f[x],z=f[f[x]],k=id(x);
	con(g[x][id(x)^1],y,id(x));
	con(y,x,id(x)^1);
	con(x,z,id(y));
	push_up(y),push_up(x);
}
void splay(int x,int pos)
{
	while(f[x]!=pos)
	{
		if(f[f[x]]==pos)rot(x);
		else if(id(x)==id(f[x]))
		rot(f[x]),rot(x);
		else rot(x),rot(x);
	}
	if(!pos)root=x;
}
void ins(int k)
{
	if(!root)
	{
		int x=++idcnt;root=x;
		v[x]=k,s[x]=c[x]=1;
		return;
	}
	int x=root,fa=0;

	while(x && v[x]!=k)
	fa=x,x=g[x][k>v[x]];
	if(x){++c[x];push_up(x);}
	else
	{
		x=++idcnt;
		v[x]=k,c[x]=s[x]=1;
		// f[x]=fa,g[fa][k>v[fa]]=x;
		con(x,fa,k>v[fa]);
	}
	push_up(fa);
	splay(x,0);
}
int find(int k)
{
	int x=root,ret=0;
	while(x)
	{
		if(k==v[x])
		{
			ret+=s[g[x][0]]+1;
			splay(x,0);
			return ret;
		}
		if(k<v[x])x=g[x][0];
		else ret+=s[g[x][0]]+c[x],x=g[x][1];
	}
	return ret;
}
int find_kth(int k)
{
	int x=root;
	while(1)
	{
		if(s[g[x][0]]<k && k<=s[g[x][0]]+c[x])
		{splay(x,0);return v[x];}
		if(k<=s[g[x][0]])x=g[x][0];
		else k-=s[g[x][0]]+c[x],x=g[x][1];
	}
	return 0;
}
int find_pre(int k)
{
	find(k);
	int x=g[root][0],ret=0;
	while(x)ret=v[x],x=g[x][1];
	return ret;
}
int find_nxt(int k)
{
	find(k);
	int x=g[root][1],ret=0;
	while(x)ret=v[x],x=g[x][0];
	return ret;
}
void del(int k)
{
	splay(find_pre(k),0);
	splay(find_nxt(k),root);
	int x=g[root][1],y=g[x][0];
	if(c[y])--c[y],--s[y];
	else g[x][0]=0;
	push_up(x),push_up(root);
}
int main()
{
	// freopen("in.txt","r",stdin);
	m=read();
	while(m--)
	{
		int opt=read(),x=read();
		if(opt==1)ins(x);
		if(opt==2)del(x);
		if(opt==3)printf("%d\n",find(x));
		if(opt==4)printf("%d\n",find_kth(x));
		if(opt==5)
		{
			ins(x);
			printf("%d\n",find_pre(x));
			del(x);
		}
		if(opt==6)
		{
			ins(x);
			printf("%d\n",find_nxt(x));
			del(x);
		}
	}
	return 0;
}