记录编号	449429	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	xzz_233	是否通过	通过
代码语言	C++	运行时间	0.286 s
提交时间	2017-09-14 13:53:33	内存使用	24.13 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define Fname "phs"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=1e6+2;
const double alpha=0.7777777;
int root,id,val[maxn],ch[maxn][2],siz[maxn],cover[maxn],b[maxn];
bool del[maxn];
il int newnode(int _val){val[++id]=_val,ch[id][0]=ch[id][1]=0,siz[id]=cover[id]=1;return id;}
il vd dfs(const int&rt){
    if(!rt)return;
    dfs(ch[rt][0]);
    if(!del[rt])b[++b[0]]=rt;
    dfs(ch[rt][1]);
}
il int divide(int l,int r){
    if(l>r)return 0;
    int mid=(l+r)>>1;
    ch[b[mid]][0]=divide(l,mid-1);
    ch[b[mid]][1]=divide(mid+1,r);
    siz[b[mid]]=siz[ch[b[mid]][0]]+siz[ch[b[mid]][1]]+!del[b[mid]];
    cover[b[mid]]=cover[ch[b[mid]][0]]+cover[ch[b[mid]][1]]+1;
    return b[mid];
}
il vd rebuild(int&rt){
    b[0]=0;dfs(rt);rt=divide(1,b[0]);
}
il int*_Insert(int&rt,const int&num){
    if(!rt){rt=newnode(num);return NULL;}
    ++siz[rt],++cover[rt];
    int*ret=_Insert(ch[rt][num>=val[rt]],num);
    if(max(cover[ch[rt][0]],cover[ch[rt][1]])>alpha*cover[rt])ret=&rt;
    return ret;
}
il vd Insert(const int&x){int*ls=_Insert(root,x);if(ls)rebuild(*ls);}
il int Rank(const int&x){
    int ret=1,now=root;
    while(now)
	if(x<=val[now])now=ch[now][0];
	else ret+=siz[ch[now][0]]+!del[now],now=ch[now][1];
    return ret;
}
il int Kth(int k){
    int now=root;
    while(now){
	if(!del[now]&&k==siz[ch[now][0]]+1)return val[now];
	if(k<=siz[ch[now][0]])now=ch[now][0];
	else k-=siz[ch[now][0]]+!del[now],now=ch[now][1];
    }
}
il vd _Erase(int k){
    int now=root;
    while(now){
	--siz[now];
	if(!del[now]&&k==siz[ch[now][0]]+1){del[now]=1;return;}
	if(k<=siz[ch[now][0]])now=ch[now][0];
	else k-=siz[ch[now][0]]+!del[now],now=ch[now][1];
    }
}
il vd Erase(const int&x){
    _Erase(Rank(x));
    if(siz[root]<cover[root]*alpha)rebuild(root);
}
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    int n=gi(),opt,x;
    while(n--){
	opt=gi(),x=gi();
	if(opt==1)Insert(x);
	else if(opt==2)Erase(x);
	else if(opt==3)printf("%d\n",Rank(x));
	else if(opt==4)printf("%d\n",Kth(x));
	else if(opt==5)printf("%d\n",Kth(Rank(x)-1));
	else printf("%d\n",Kth(Rank(x+1)));
    }
    return 0;
}