记录编号	478265	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	lyqlyqcogs	是否通过	通过
代码语言	C++	运行时间	0.421 s
提交时间	2017-12-10 11:25:21	内存使用	2.60 MiB

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

#define gc getchar()

int cnt[N], siz[N], ch[N][2], fa[N], data[N];
int Ti, nn, root;

inline int read(){
    int x = 0, f = 1; char c = gc;
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = gc;}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x * f;
}

void pushup(int rt){
    siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + cnt[rt];
}

void ins(int &rt, int x){
    if(!rt) {rt = ++ nn; data[nn] = x; siz[nn] = cnt[nn] = 1; return ;}
    if(data[rt] == x) {siz[rt] ++; cnt[rt] ++; return ;}
    if(x < data[rt]) {ins(ch[rt][0], x); fa[ch[rt][0]] = rt; pushup(rt);}
    else {ins(ch[rt][1], x); fa[ch[rt][1]] = rt; pushup(rt);}
}

int son(int x){
    return x == ch[fa[x]][1];
}

void rotate(int x){
    int y = fa[x], z = fa[y], b = son(x), c = son(y), a = ch[x][!b];
    if(z) ch[z][c] = x; else root = x; fa[x] = z;
    if(a) fa[a] = y; ch[y][b] = a; 
	ch[x][!b] = y; fa[y] = x; pushup(y); pushup(x); 
}

void splay(int x, int i){
    while(fa[x] != i){
        int y = fa[x], z = fa[y];
        if(z == i) rotate(x);
        else if(son(x) == son(y)) rotate(y), rotate(x);
        else rotate(x), rotate(x);
    }
}

int getmn(int rt){
    int p = rt, ans = -1;
    while(p) {ans = p; p = ch[p][0];}
    return ans;
}

void del(int rt, int x){
    if(data[rt] == x){
        if(cnt[rt] > 1) cnt[rt] --, siz[rt] --;
        else{
            splay(rt, 0); int p = getmn(ch[rt][1]);
            if(p != -1){
                splay(p, rt); root = p; fa[p] = 0; ch[p][0] = ch[rt][0];
                fa[ch[rt][0]] = p; pushup(p);
            }
            else {root = ch[rt][0]; fa[root] = 0; }
        }
        return ;
    }
    if(x < data[rt]) del(ch[rt][0], x), pushup(rt);
    else del(ch[rt][1], x), pushup(rt);
}

int getk(int rt, int k){
    if(data[rt] == k){
        splay(rt, 0);
        return siz[ch[rt][0]] + 1;
    }
    if(k < data[rt]) return getk(ch[rt][0], k);
    else return getk(ch[rt][1], k);
}

int getkth(int rt, int k){
    int l = ch[rt][0];
    if(siz[l] < k && siz[l] + cnt[rt] >= k) return data[rt];
    else if(siz[l] >= k) return getkth(ch[rt][0], k);
    else return getkth(ch[rt][1], k - siz[l] - cnt[rt]);
}

int getpre(int rt, int x){
    int p = rt, ans;
    while(p){
        if(x <= data[p]) p = ch[p][0];
        else {ans = p; p = ch[p][1];}
    }
    return ans;
}

int getsuc(int rt, int x){
    int p = rt, ans;
    while(p){
        if(x >= data[p]) p = ch[p][1];
        else {ans = p;p = ch[p][0];}
    }
    return ans;
}

int main()
{
	freopen("phs.in", "r", stdin);
	freopen("phs.out", "w", stdout);
    Ti = read();
    while(Ti --){
        int opt = read(), x = read();
        if(opt == 1) ins(root, x);
        else if(opt == 2) del(root, x);
        else if(opt == 3) printf("%d\n", getk(root, x));
        else if(opt == 4) printf("%d\n", getkth(root, x));
        else if(opt == 5) printf("%d\n", data[getpre(root, x)]);
        else printf("%d\n", data[getsuc(root, x)]);
    }
    
    return 0;
}