记录编号	392322	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tb的平衡树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.747 s
提交时间	2017-04-07 19:14:32	内存使用	3.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{
	const int _size_=1<<20;
	char is[_size_],*pi=is,*iend=is+_size_,os[_size_],*po=os,*oend=os+_size_;
	template<class T>Anti Leaf void readint(register T &x){
		register int neg=0;
		x=0;
		do{
			++pi;
			if(pi==iend)fread(pi=is,_size_,sizeof(char),stdin);
		}while(*pi<'-');
		if(*pi=='-'){
			neg=1;
			++pi;
			if(pi==iend)fread(pi=is,_size_,sizeof(char),stdin);
		}
		while(*pi>47){
			x=x*10+(*pi^48);
			++pi;
			if(pi==iend)fread(pi=is,_size_,sizeof(char),stdin);
		}
		if(neg)x=-x;
	}
	template<class T>Anti Leaf void writeint(register T x){
		static int a[25];
		if(x<0){
			*po++='-';
			if(po==oend)fwrite(po=os,_size_,sizeof(char),stdout);
			x=-x;
		}
		register int i=0;
		do{
			a[i++]=x%10^48;
			x/=10;
		}while(x);
		for(--i;~i;--i){
			*po++=a[i];
			if(po==oend)fwrite(po=os,_size_,sizeof(char),stdout);
			x=-x;
		}
		*po++='\n';
		if(po==oend)fwrite(po=os,_size_,sizeof(char),stdout);
	}
}
using namespace mine;
int qsum(int,int);
int kth(int);
int n,d,x,a[maxn]={0};
Anti 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]));
	}
	fwrite(os,po-os,sizeof(char),stdout);
	return 0;
}
Anti Leaf 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;
}
Anti Leaf 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;
}