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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=140010,M=131072;
namespace mine{
	template<class T>inline void readint(T &__x){
		static int __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)__x=-__x;
	}
	template<class T>inline void writeint(register T __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10^48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
		putchar('\n');
	}
}
using namespace mine;
int qsum(int,int);
int kth(int);
int n,d,x,a[maxn<<1]={0};
int main(){
	freopen("tb_kp.in","r",stdin);
	freopen("tb_kp.out","w",stdout);
	scanf("%d",&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;
}