记录编号	373663	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	6.907 s
提交时间	2017-02-21 15:51:35	内存使用	12.96 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
const int maxn=1105000;
int ch[maxn][2],size[maxn],root,cnt;
int n,full,fix;
int Min(){
	int rt=root,res=0;
	for(int i=full;~i;i--){
		if(ls(rt) && size[ls(rt)]>0)rt=ls(rt);
		else rt=rs(rt),res|=1<<i;
	}
	return res-fix;
}
int Max(){
	int rt=root,res=0;
	for(int i=full;~i;i--){
		if(rs(rt) && size[rs(rt)])rt=rs(rt),res|=1<<i;
		else rt=ls(rt);
	}
	return res-fix;
}
void Insert(int x,int add){x+=fix;
	int rt=root;
	for(int i=full;~i;i--){
		bool op=x>>i&1;
		if(!ch[rt][op])ch[rt][op]=++cnt;
		rt=ch[rt][op];
		size[rt]+=add;
	}
}
int Rank(int x){x+=fix;
	int rt=root,res=0;
	for(int i=full;~i;i--){
		bool op=x>>i&1;
		if(op)res+=size[ls(rt)],rt=rs(rt);
		else rt=ls(rt);
	}
	return res;
}
int kth(int k){
	int rt=root,res=0;
	for(int i=full;~i;i--){
		if(k>size[ls(rt)])k-=size[ls(rt)],rt=rs(rt),res|=1<<i;
		else rt=ls(rt);
	}
	return res-fix;
}
int Prev(int x){
	int _rank=Rank(x);
	if(_rank==0)return -0x3f3f3f3f;
	return kth(_rank);
}
int Succ(int x){
	int _rank=Rank(x+1);
	if(_rank==size[ls(root)]+size[rs(root)])return 0x3f3f3f3f;
	return kth(_rank+1);
}
void Init();
int main(){
	freopen("tb_kp.in","r",stdin);freopen("tb_kp.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	root=++cnt;
	full=17;fix=32769;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int type,x;scanf("%d",&type);
		if(type==7)printf("%d\n",Min());
		else if(type==8)printf("%d\n",Max());
		else {
			scanf("%d",&x);
			if(type==1)Insert(x,1);
			else if(type==2)Insert(x,-1);
			else if(type==3)printf("%d\n",Rank(x)+1);
			else if(type==4)printf("%d\n",kth(x));
			else if(type==5)printf("%d\n",Prev(x));
			else if(type==6)printf("%d\n",Succ(x));
		}
	}
}