平衡树做法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int rt,tot;
int sz[N],val[N],cnt[N];
int fa[N],ch[N][2];

struct Splay{
	
	void maintain(int x)
	{
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
	}
	
	bool get(int x)
	{
		return x==ch[fa[x]][1];
	}
	
	void clear(int x)
	{
		sz[x]=val[x]=cnt[x]=fa[x]=ch[x][0]=ch[x][1]=0;
	}
	
	void retate(int x)
	{
		int y=fa[x],z=fa[y],chk=get(x);
		ch[y][chk]=ch[x][chk^1];
		if(ch[x][chk^1])	fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y;
		fa[x]=z;
		fa[y]=x;
		if(z)	ch[z][y==ch[z][1]]=x;
		maintain(y);
		maintain(x);
	}
	
	void splay(int x)
	{
		for(int f=fa[x];f=fa[x],f;retate(x))
			if(fa[f])	retate(get(x)==get(f)?f:x);
		rt=x;
	}
	
	void ins(int k)
	{
		if(!rt)
		{
			val[++tot]=k;
			cnt[tot]++;
			rt=tot;
			maintain(rt);
			return;
		}
		int cur=rt,f=0;
		while(1)
		{
			if(val[cur]==k)
			{
				cnt[cur]++;
				maintain(cur);
				maintain(f);
				splay(cur);
				break;
			}
			f=cur;
			cur=ch[cur][val[cur]<k];
			if(!cur)
			{
				val[++tot]=k;
				cnt[tot]++;
				fa[tot]=f;
				ch[f][val[f]<k]=tot;
				maintain(tot);
				maintain(f);
				splay(tot);
				break;
			}
		}
	}
	
	int rk(int k)
	{
		int res=0,cur=rt;
		while(1)
		{
			if(k<val[cur])
				cur=ch[cur][0];
			else
			{
				res+=sz[ch[cur][0]];
				if(k==val[cur])
				{
					splay(cur);
					return res+1;
				}
				res+=cnt[cur];
				cur=ch[cur][1];
			}
		}
	}
	
	int kth(int k)
	{
		int cur=rt;
		while(1)
		{
			if(ch[cur][0]&&k<=sz[ch[cur][0]])
				cur=ch[cur][0];
			else
			{
				k-=cnt[cur]+sz[ch[cur][0]];
				if(k<=0)
				{
					splay(cur);
					return val[cur];
				}
				cur=ch[cur][1];
			}
		}
	}
	
	int pre()
	{
		int cur=ch[rt][0];
		if(!cur)	return cur;
		while(ch[cur][1])	cur=ch[cur][1];
		splay(cur);
		return cur;
	}
	
	int nxt()
	{
		int cur=ch[rt][1];
		if(!cur)	return cur;
		while(ch[cur][0])	cur=ch[cur][0];
		splay(cur);
		return cur;
	}
	
	void del(int k)
	{
		rk(k);
		if(cnt[rt]>1)
		{
			cnt[rt]--;
			maintain(rt);
			return;
		}
		if(!ch[rt][0]&&!ch[rt][1])
		{
			clear(rt);
			rt=0;
			return;
		}
		if(!ch[rt][0])
		{
			int cur=rt;
			rt=ch[rt][1];
			fa[rt]=0;
			clear(cur);
			return;
		}
		if(!ch[rt][1])
		{
			int cur=rt;
			rt=ch[rt][0];
			fa[rt]=0;
			clear(cur);
			return;
		}
		int cur=rt;
		int x=pre();
		fa[ch[cur][1]]=x;
		ch[x][1]=ch[cur][1];
		clear(cur);
		maintain(rt);
	}
}tree;

int main()
{
	int n,opt,x;
	for(scanf("%d",&n);n;--n)
	{
		scanf("%d%d",&opt,&x);
		switch(opt)
		{
			case 1:
				tree.ins(x);
				break;
			case 2:
				tree.del(x);
				break;
			case 3:
				printf("%d\n",tree.rk(x));
				break;
			case 4:
				printf("%d\n",tree.kth(x));
				break;
			case 5:
				tree.ins(x);
				printf("%d\n",val[tree.pre()]);
				tree.del(x);
				break;
			case 6:
				tree.ins(x);
				printf("%d\n",val[tree.nxt()]);
				tree.del(x);
				break;
		}
	}	
	return 0;
}