记录编号	371664	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	4.933 s
提交时间	2017-02-16 16:33:21	内存使用	1.73 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char ch;int ff;inline void R_int(int &x){
	while(ch=getchar(),ch<'!');
	if(ch=='-')ch=getchar(),ff=-1;else ff=1;
	x=ch-48;
	while(ch=getchar(),ch>'!')x=x*10+ch-48;
	x*=ff;
}
const int SIZEN=32768,maxn=SIZEN*4+5,INF=0x3f3f3f3f,N=16;
struct Rabit_tree{
	int RT,ch[maxn][2],size[maxn],cnt;
	Rabit_tree(){RT=cnt=1;}
	int sz(){return size[RT];}
	void set(int key,int v=1){
		int p=RT;bool c;size[p]+=v;
		for(int i=N;~i;i--){
			c=key>>i&1;
			if(!ch[p][c])ch[p][c]=++cnt;
			p=ch[p][c],size[p]+=v;
		}
	}
	int sum(int key){
		key++;int p=RT,res=0;bool c;
		for(int i=N;~i;i--){
			c=key>>i&1;
			if(c)res+=size[ch[p][0]];
			p=ch[p][c];
		}
		return res;
	}
	int get(int th){
		int p=RT,res=0;
		for(int i=N;~i;i--){
			if(th>size[ch[p][0]])
				res|=1<<i,th-=size[ch[p][0]],p=ch[p][1];
			else p=ch[p][0];
		}
		return res;
	}
}Trie;
int main(){
	freopen("tb_kp.in","r",stdin);freopen("tb_kp.out","w",stdout);
	int n,ope,x,th;R_int(n);
	while(n--){
		R_int(ope);
		if(ope==7)printf("%d\n",Trie.get(1)-SIZEN);
		else if(ope==8)printf("%d\n",Trie.get(Trie.sz())-SIZEN);
		else{
			R_int(x);
			if(ope==1)Trie.set(x+SIZEN,1);
			else if(ope==2)Trie.set(x+SIZEN,-1);
			else if(ope==3)printf("%d\n",Trie.sum(x+SIZEN-1)+1);
			else if(ope==4)printf("%d\n",Trie.get(x)-SIZEN);
			else if(ope==5){
				th=Trie.sum(x+SIZEN-1)+1;
				printf("%d\n",th==1?-INF:Trie.get(th-1)-SIZEN);
			}
			else {
				th=Trie.sum(x+SIZEN);
				printf("%d\n",th==Trie.sz()?INF:Trie.get(th+1)-SIZEN);
			}
		}
	}
}