记录编号	366434	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.584 s
提交时间	2017-01-24 00:24:40	内存使用	1.05 MiB

#include<cstdio>
int min(int x,int y){return x<y?x:y;}
const int N=2e5+10,size=1<<16;
int n,s[N];
#define lc x<<1
#define rc (x<<1)|1
void add(int p,int d){
	int x=1,l=0,r=size;
	while (1){
		s[x]+=d;
		if (l==r) return;
		int mid=(l+r)>>1;
		if (p>mid) x=rc,l=mid+1;
			else x=lc,r=mid;
	}
}
int rank(int k){
	int x=1,l=0,r=size,ans=1;
	while (l<r){
		int mid=(l+r)>>1;
		if (k>mid) ans+=s[lc],x=rc,l=mid+1;
			else x=lc,r=mid;
	}
	return ans;
}
int find(int R){
	int x=1,l=0,r=size;
	while (l<r){
		int mid=(l+r)>>1;
		if (R>s[lc]) R-=s[lc],x=rc,l=mid+1;
			else x=lc,r=mid;
	}
	return l-(1<<15);
}
int pred(int k){
	int R=rank(k);
	return R>1?find(R-1):-0x3f3f3f3f;
}
int succ(int k){
	int R=rank(k+1);
	return R<=s[1]?find(R):0x3f3f3f3f;
}
int read(){
	int x=0;bool sign=1;char ch=getchar();
	while ((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
	if (ch=='-') sign=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return sign?x:-x;
}
int main()
{
	freopen("tb_kp.in","r",stdin);
	freopen("tb_kp.out","w",stdout);
	n=read();
	while (n--){
		int tp=read(),x;
		if (tp<=6) x=read();
		if (tp==1) add(x+(1<<15),1);
		if (tp==2) add(x+(1<<15),-1);
		if (tp==3) printf("%d\n",rank(x+(1<<15)));
		if (tp==4) printf("%d\n",find(x));
		if (tp==5) printf("%d\n",pred(x+(1<<15)));
		if (tp==6) printf("%d\n",succ(x+(1<<15)));
		if (tp==7) printf("%d\n",find(1));
		if (tp==8) printf("%d\n",find(s[1]));
	}
	return 0;
}