记录编号	459699	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.246 s
提交时间	2017-10-13 15:40:45	内存使用	5.27 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=1e5+10;
int n;
struct cc{
	int c,x;
}c[maxn];
struct dd{
	int x,id;
	inline bool operator < (const dd & a)const {
		return x<a.x;
	}
}data[maxn];
int ctot;
int rk[maxn];
int sum[maxn<<3];
inline void change(int o,int l,int r,int nl,int nr,int v){
	if(l>=nl&&r<=nr){
		sum[o]+=v;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)change(ls,l,m,nl,nr,v);
	if(m<nr)change(rs,m+1,r,nl,nr,v);
	sum[o]=sum[ls]+sum[rs];
}
inline int kth(int o,int l,int r,int k){
	if(l==r)return l;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int lsum=sum[ls];
	if(k<=lsum)return kth(ls,l,m,k);
	else return kth(rs,m+1,r,k-lsum);
}
inline int find(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return sum[o];
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int ans=0;
	if(m>=nl)ans+=find(ls,l,m,nl,nr);
	if(m<nr)ans+=find(rs,m+1,r,nl,nr);
	return ans;
}
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		c[i].c=read();
		c[i].x=read();
		data[i].x=c[i].x;
		data[i].id=i;
	}
	sort(data+1,data+n+1);
	for(int i=1;i<=n;i++){
		if(data[i].x==data[i-1].x)rk[data[i].id]=ctot;
		else {rk[data[i].id]=i;ctot=i;}
	}
	for(int i=1;i<=n;i++){
		if(c[i].c==1){
			change(1,1,n,rk[i],rk[i],1);
		} 
		if(c[i].c==2){
			change(1,1,n,rk[i],rk[i],-1);
		}
		if(c[i].c==3){
			if(rk[i]-1==0){puts("1");continue;}
			printf("%d\n",find(1,1,n,1,rk[i]-1)+1);
		}
		if(c[i].c==4){
			printf("%d\n",data[kth(1,1,n,c[i].x)].x);
		}
		if(c[i].c==5){
			int tot=find(1,1,n,1,rk[i]-1);
			printf("%d\n",data[kth(1,1,n,tot)].x);
		}
		if(c[i].c==6){
			int tot=find(1,1,n,1,rk[i]);
			printf("%d\n",data[kth(1,1,n,tot+1)].x);
		}
	}
	return 0;
}