Tyvj 1728 普通平衡树

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
	struct Node
	{
		int ch[2],siz;
		ll key,val;
	};
	vector<Node> v;
	int root;
	FhqTreap():v(1),root(0) {}
	void push_up(int k)
	{
		v[k].siz=v[v[k].ch[0]].siz+v[v[k].ch[1]].siz+1;
	}
	int merge(int a,int b)
	{
		if(!a||!b)return a+b;
		if(v[a].key<v[b].key)
			return v[a].ch[1]=merge(v[a].ch[1],b),push_up(a),a;
		return v[b].ch[0]=merge(a,v[b].ch[0]),push_up(b),b;
	}
	void splitVal(int a,ll w,int &l,int &r)//按值将树划分，使得左子树上的值恰小于w
	{
		if(!a)l=r=0;
		else if(v[a].val>w)splitVal(v[a].ch[0],w,l,v[a].ch[0]),push_up(r=a);
		else splitVal(v[a].ch[1],w,v[a].ch[1],r),push_up(l=a);
	}
	void insert(ll x)
	{
		int a,b;
		v.push_back(Node { {0,0},1,rand(),x});
		splitVal(root,x,a,b),root=merge(merge(a,v.size()-1),b);
	}
	void erase(ll x)
	{
		int a,b,c;
		splitVal(root,x,a,b),splitVal(a,x-1,a,c);
		root=merge(merge(a,merge(v[c].ch[0],v[c].ch[1])),b);
	}
	ll kth(int k)
	{
		for(int u=root,ls;;)
		{
			if(ls=v[v[u].ch[0]].siz,ls+1==k)
				return v[u].val;
			if(ls<k)k-=ls+1,u=v[u].ch[1];
			else u=v[u].ch[0];
		}
	}
	int lower_bound(ll x)
	{
		return upper_bound(x-1);
	}
	int upper_bound(ll x)
	{
		int a,b,ret;
		return splitVal(root,x,a,b),ret=v[a].siz+1,root=merge(a,b),ret;
	}
};
int main()
{
	int n,o,x;
	FhqTreap t;
	for(scanf("%d",&n); n--;)
	{
		scanf("%d%d",&o,&x);
		if(o==1)t.insert(x);
		else if(o==2)t.erase(x);
		else printf("%d\n",o==3?t.lower_bound(x):
						t.kth(o==4?x:
							  o==5?t.lower_bound(x)-1:
							  t.upper_bound(x)));
	}
}