记录编号	392299	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2591.[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.024 s
提交时间	2017-04-07 19:01:50	内存使用	2.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Anti __attribute__((optimize("-Os")))
#define Leaf __inline__ __attribute__((always_inline))
#define dir(x) ((x)==(x)->p->ch[1])
using namespace std;
const int maxn=262200,M=131072;
namespace mine{
	#define siz (1<<20)
	#define frd fread(hd=buf,1,siz,stdin)
	#define getchar() (hd==tl?(frd,*hd++):*hd++)
	char buf[siz],*hd=buf+siz,*tl=buf+siz;
	template<class T>Anti Leaf void readint(register T &x){
		register int c,neg=0;
		x=0;
		do c=getchar();while(c<'-');
		if(c=='-'){
			neg=1;
			c=getchar();
		}
		for(;c>47;c=getchar())x=x*10+(c^48);
		if(neg)x=-x;
	}
	template<class T>Anti Leaf void writeint(register T x){
		static int a[25];
		if(x<0){
			putchar('-');
			x=-x;
		}
		register int i=0;
		do{
			a[i++]=x%10^48;
			x/=10;
		}while(x);
		for(--i;~i;--i)putchar(a[i]);
		putchar('\n');
	}
}
using namespace mine;
int qsum(int,int);
int kth(int);
int n,d,x,a[maxn]={0};
int main(){
	freopen("tb_kp.in","r",stdin);
	freopen("tb_kp.out","w",stdout);
	readint(n);
	while(n--){
		readint(d);
		if(d<7)readint(x);
		if(d!=4)x+=32768;
		if(d==1)for(x+=M;x;x>>=1)a[x]++;
		else if(d==2)for(x+=M;x;x>>=1)a[x]--;
		else if(d==3)writeint(qsum(1,x-1)+1);
		else if(d==4)writeint(kth(x));
		else if(d==5){
			d=qsum(1,x-1);
			writeint(d?kth(d):-0x3f3f3f3f);
		}
		else if(d==6){
			d=qsum(1,x)+1;
			writeint(d?kth(d):0x3f3f3f3f);
		}
		else if(d==7)writeint(kth(1));
		else writeint(kth(a[1]));
	}
	return 0;
}
inline int qsum(register int l,register int r){
	register int ans=0;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans+=a[l^1];
		if(r&1)ans+=a[r^1];
	}
	return ans;
}
inline int kth(register int k){
	register int rt=1;
	while(rt<M)if(a[rt<<=1]<k){
		k-=a[rt];
		rt^=1;
	}
	return rt-M-32768;
}