记录编号	537409	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.371 s
提交时间	2019-07-12 08:55:27	内存使用	42.28 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 1e9
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
const int maxn=100050*25;
int full,fix=1e7;
int n,cnt=1,ch[maxn][2],size[maxn];
void Insert(int x,int add){
	x+=fix;
	int rt=1;
	for(int i=full;i>=0;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=1,res=0;
	for(int i=full;i>=0;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 res=0,rt=1;
	for(int i=full;~i;i--){
		if(k>size[ls(rt)]) k-=size[ls(rt)],res|=1<<i,rt=rs(rt);
		else rt=ls(rt);
	}
	return res-fix;
}
void Init();
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d",&n);
	full=log2(fix+fix);
	for(int i=1;i<=n;i++){
		int type,x;scanf("%d%d",&type,&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",kth(Rank(x)));
		else if(type==6) printf("%d\n",kth(Rank(x+1)+1)); 
	}
}