替罪羊树

const int MAXN=1e5+5;
namespace scapegoat_tree{
	#define lch(k) node[node[k].lch]
	#define rch(k) node[node[k].rch]
	const double alpha=0.75,del_x=0.4,inf=1e9;
	struct Node{
		int lch,rch,v,sz,tot;
		bool exist;
	}node[MAXN];
	int node_cnt;
	int new_node(int val){
		int k=++node_cnt;
		node[k].lch=node[k].rch=0;
		node[k].v=val;
		node[k].sz=node[k].tot=1;
		node[k].exist=true;
		return k;
	}
	int root,a[MAXN],n;
	bool isbad(int k){
		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
	}
	bool isbad_2(int k){
		return del_x*node[k].tot>node[k].sz;
	}
	void build(int &k,int lef,int rig){
		if(lef>rig) return k=0,void();
		int mid=lef+rig>>1;
		k=a[mid];
		if(lef==rig){
			node[k].lch=node[k].rch=0;
			node[k].sz=node[k].tot=1;
			return;
		}
		build(node[k].lch,lef,mid-1);
		build(node[k].rch,mid+1,rig);
		node[k].tot=node[k].sz=lch(k).sz+rch(k).sz+1;
	}
	void dfs(int k){
		if(!k)return;
		dfs(node[k].lch);
		if(node[k].exist)a[++n]=k;
		dfs(node[k].rch);
	}
	void rebuild(int &k){
		n=0;
		dfs(k);
		build(k,1,n);
	}
	void check(int &k,int v){
		if(k){
			if(isbad(k)||isbad_2(k))
			rebuild(k);
			else if(v<node[k].v)
			check(node[k].lch,v);
			else
			check(node[k].rch,v);
		}
	}
	int rank(int v){// 返回小于 v 的个数+1 
		int k=root,rk=1;
		while(k){
			if(v<=node[k].v)
			k=node[k].lch;
			else{
				rk+=lch(k).sz+node[k].exist;
				k=node[k].rch;
			}
		}
		return rk;
	}
	int kth(int rk){// 返回第 rk 小的数 
		int k=root;
		while(k){
			if(lch(k).sz+1==rk&&node[k].exist)return node[k].v;
			if(lch(k).sz+node[k].exist>=rk)
			k=node[k].lch;
			else{
				rk-=lch(k).sz+node[k].exist;
				k=node[k].rch;
			}
		}
		return inf;
	}
	void Insert(int &k,int v){
		if(!k){
			k=new_node(v);
			return;
		}
		node[k].sz++;node[k].tot++;
		if(v<node[k].v)
		Insert(node[k].lch,v);
		else
		Insert(node[k].rch,v);
	}
	void Insert(int v){
		Insert(root,v);
		check(root,v);
	}
	void Delate(int k,int rk){
		node[k].sz--;
		if(lch(k).sz+1==rk&&node[k].exist){
			node[k].exist=false;
			return;
		}
		if(lch(k).sz+node[k].exist>=rk)
		Delate(node[k].lch,rk);
		else
		Delate(node[k].rch,rk-lch(k).sz-node[k].exist);
	}
	void Delate(int v){
		Delate(root,rank(v));
		check(root,v);
	}
	int pre(int v){// 返回一个严格比 v 小的数 
		return kth(rank(v)-1);
	}
	int suf(int v){// 返回一个严格比 v 大的数 
		return kth(rank(v+1));
	} 
	#undef lch
	#undef rch
}
int main()
{
	int q=read_int(),opt,x;
	while(q--){
		opt=read_int(),x=read_int();
		switch(opt){
			case 1:
				scapegoat_tree::Insert(x);
				break;
			case 2:
				scapegoat_tree::Delate(x);
				break;
			case 3:
				enter(scapegoat_tree::rank(x));
				break;
			case 4:
				enter(scapegoat_tree::kth(x));
				break;
			case 5:
				enter(scapegoat_tree::pre(x));
				break;
			case 6:
				enter(scapegoat_tree::suf(x));
				break;
		}
	}
	return 0;
}