记录编号	432570	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.289 s
提交时间	2017-08-03 15:47:49	内存使用	0.55 MiB

#include <stdio.h>
#include <cstring>
#define R register
#define fast __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline)) 
const int full = 1<<30;
const int fix = 10000000;
int n;


fast IL int read(){
    R int x=0,f=1;
    R char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

struct node{
    node *ch[2];
    int sum;
    void* operator new(size_t);
}*null=new node,*C,*mempool,*root;

fast IL void* node :: operator new(size_t){
    if(C==mempool){
        C=new node[1<<15];
        mempool=C+(1<<15);
    }
    C->ch[0]=C->ch[1]=null;
    C->sum=0;
    return C++;
}

fast IL void insert(R int x,R int add){
    node *rt=root;x+=fix;
    for(R int i=30;~i;i--){
        R int d = x&(1<<i)?1:0;
        if(rt->ch[d]==null)rt->ch[d]=new node;
        rt=rt->ch[d];
        rt->sum+=add;
    }
}

fast IL int Rank(R int x){
    x+=fix;R int Ans=0;
    node *rt=root;
    for(R int i=30;~i;i--){
        if(x&(1<<i))Ans+=rt->ch[0]->sum,rt=rt->ch[1];
        else rt=rt->ch[0];
    }
    return Ans+1;
}

fast IL int kth(R int k){
    node *rt=root;
    R int Ans=0;
    for(R int i=30;~i;i--){
        if(k>rt->ch[0]->sum)Ans|=1<<i,k-=rt->ch[0]->sum,rt=rt->ch[1];
        else rt=rt->ch[0];
    }
    return Ans-fix;
}

int main(){
    null->ch[0]=null->ch[1]=null;
    root = new node;
    freopen("phs.in","r",stdin);
    freopen("phs.out","w",stdout);
    n=read();
    while(n--){
        int op=read(),x=read();
        switch(op){
            case 1:insert(x,1);break;
            case 2:insert(x,-1);break;
            case 3:printf("%d\n",Rank(x));break;
            case 4:printf("%d\n",kth(x));break;
            case 5:printf("%d\n",kth(Rank(x)-1));break;
            case 6:printf("%d\n",kth(Rank(x+1)));break;
        }
    }
}