记录编号	467107	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	4.539 s
提交时间	2017-10-30 08:13:16	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
const int ADD(32768);
const int inf(0x3f3f3f3f);
#define get_size(x) (x?x->size:0)
struct node{
	node *ch[2];int size;
	//node():size(0){ch[0]=ch[1]=NULL;}
}*root,*null;
inline node* newnode(){
	node *tmp(new node);
	tmp->ch[0]=tmp->ch[1]=null;tmp->size=0;return tmp;
}
inline void insert(node *&x,int key,int dep){
	if(x==null)x=newnode();++x->size;if(dep==-1)return;
	int tmp((key>>dep)&1);insert(x->ch[tmp],key,dep-1);
}
inline void del(node *&x,int key,int dep){
	--x->size;if(dep==-1)return;
	int tmp((key>>dep)&1);del(x->ch[tmp],key,dep-1);
}
inline int Rank(int x){
	node *now(root);int ret(0),dep(16);
	for(;dep>=0;--dep){
//		if(!now)return ret;
		int tmp((x>>dep)&1);
		if(tmp)ret+=now->ch[0]->size;
		now=now->ch[tmp];
	}
	return ret;
}
inline int kth(int k){
	node *now(root);int dep(16),ret(0);
	for(;dep>=0;--dep){
//		if(!now)return ret;
		if(now->ch[0]->size>=k)now=now->ch[0];
		else k-=now->ch[0]->size,now=now->ch[1],ret|=1<<dep;
	}
	return ret;
}
int n;
int main(){
	freopen("tb_kp.in","r",stdin);freopen("tb_kp.out","w",stdout);
	null=new node;null->ch[0]=null->ch[1]=null;root=null;
	n=read();
	while(n--){
		int op(read());
		if(op==7){printf("%d\n",kth(1)-ADD);continue;}
		if(op==8){printf("%d\n",kth(root->size)-ADD);continue;}
		int x(read());
		if(op==1)insert(root,x+ADD,16);
		if(op==2)del(root,x+ADD,16);
		if(op==3)printf("%d\n",Rank(x+ADD)+1);
		if(op==4)printf("%d\n",kth(x)-ADD);
		if(op==5){int tmp(Rank(x+ADD)+1);if(tmp==1)printf("%d\n",-inf);else printf("%d\n",kth(tmp-1)-ADD);}
		if(op==6){int tmp(Rank(x+ADD+1));if(tmp==get_size(root))printf("%d\n",inf);else printf("%d\n",kth(tmp+1)-ADD);}
	}
}