记录编号	554068	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Restly	是否通过	通过
代码语言	C++	运行时间	0.448 s
提交时间	2020-09-07 20:36:22	内存使用	3.34 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 100005
int key[maxn],ch[maxn][2],f[maxn],size[maxn],cnt[maxn],n,sz = 0,root = 0;
inline void clear(register int x){
    key[x] = ch[x][0] = ch[x][1] = f[x] = size[x] = cnt[x] = 0;
    return ;
}
inline int get(register int x){
    return ch[f[x]][1] == x;
}
inline void pushup(register int x){
    if(x){
        size[x] = cnt[x];
        if(ch[x][0])size[x] += size[ch[x][0]];
        if(ch[x][1])size[x] += size[ch[x][1]];
    }
}
inline void rotate(register int x){
    int old = f[x],oldf = f[f[x]],which = get(x);
    ch[old][which] = ch[x][which ^ 1];
    f[ch[old][which]] = old;
    f[old] = x;
    ch[x][which ^ 1] = old;
    f[x] = oldf;
    if(oldf)ch[oldf][ch[oldf][1] == old] = x;
    pushup(old);
    pushup(x);
    return ;
}
inline void splay(register int x){
    for(int fa;fa = f[x];rotate(x)){
        if(f[fa]){
            rotate(get(fa) == get(x) ? fa : x);
        }
    }
    root = x;
    return ;
}
inline void insert(register int x){
    if(root == 0){
        ++ sz;
        root = sz;
        cnt[root] = size[root] = 1;
        f[root] = ch[root][0] = ch[root][1] = 0;
        key[root] = x;
        return ;
    }
    int now = root,fa = 0;
    while(23){
        if(key[now] == x){
            ++ cnt[now];
            pushup(now);
            pushup(fa);
            splay(now);
            return ;
        }
        fa = now;
        now = ch[now][x > key[now]];
        if(now == 0){
            ++ sz;
            now = sz;
            f[sz] = fa;
            ch[fa][x > key[fa]] = sz;
            ch[sz][0] = ch[sz][1] = 0;
            key[sz] = x;
            cnt[sz] = size[sz] = 1;
            pushup(fa);
            splay(now);
            return ;
        }
    }
    return ;
}
inline int rnk(register int x){
    int now = root,ans = 0;
    while(1){
        if(key[now] > x){
            now = ch[now][0];
        }
        else{
            ans += size[ch[now][0]];
            if(key[now] == x){
                splay(now);
                return ans + 1;
            }
            ans += cnt[now];
            now = ch[now][1];
        }
    }
    return 0;
}
inline int kth(register int x){
    int now = root;
    while(1){
        if(ch[now][0]&&x <= size[ch[now][0]]){
            now = ch[now][0];
        }
        else{
            int temp = size[ch[now][0]] + cnt[now];
            if(x <= temp){
                return key[now];
            }
            x -= temp;
            now = ch[now][1];
        }
    }
    return 0;
}
inline int pre(){
    int now = ch[root][0];
    while(ch[now][1])now = ch[now][1];
    return now;
}
inline int next(){
    int now = ch[root][1];
    while(ch[now][0])now = ch[now][0];
    return now;
}
inline void del(register int x){
    rnk(x);
    if(cnt[root] > 1){
        -- cnt[root];
        pushup(root);
        return ;
    }
    if(!ch[root][0]&&!ch[root][1]){
        clear(root);
        root = 0;
        return ;
    } 
    if(!ch[root][0]){
        int oldroot = root;
        root = ch[root][1];
        clear(oldroot);
        f[root] = 0;
        return ;
    }
    else if(!ch[root][1]){
        int oldroot = root;
        root = ch[root][0];
        clear(oldroot);
        f[root] = 0;
        return ;
    }
    int oldroot = root,leftbig = pre();
    splay(leftbig);
    ch[root][1] = ch[oldroot][1];
    f[ch[oldroot][1]] = root;
    clear(oldroot);
    pushup(root);
    return ;
}
int k,x;
int main()
{
    freopen("phs.in","r",stdin);
    freopen("phs.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i)
    {
        scanf("%d%d",&k,&x);
        if(k == 1)
        {
            insert(x);
        }
        if(k == 2)
        {
            del(x);
        }
        if(k == 3)
        {
            printf("%d\n",rnk(x));
        }
        if(k == 4)
        {
            printf("%d\n",kth(x));   
        }
        if(k == 5)
        {
            insert(x);
            printf("%d\n",key[pre()]);
            del(x);
        }
        if(k == 6)
        {
            insert(x);
            printf("%d\n",key[next()]);
            del(x);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}