萌新求调 Splay 88pts

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 1e5 + 9;
struct node {
    int val, s[2], fa, siz, cnt;
} T[N];
inline void pushup(int id) {
    T[id].siz = T[T[id].s[0]].siz + T[T[id].s[1]].siz + T[id].cnt;
    if (T[id].s[0]) T[T[id].s[0]].fa = id;
    if (T[id].s[1]) T[T[id].s[1]].fa = id;
//    T[T[id].s[0]].fa = T[T[id].s[1]].fa = id;
}
int n, rt;
inline void rotate(int u) {
    int v = T[u].fa, w = T[v].fa, fl = (T[v].s[1] == u);
    T[u].fa = w;
    if (w) T[w].s[T[w].s[1] == v] = u;
    T[v].s[fl] = T[u].s[fl ^ 1];
    T[u].s[fl ^ 1] = v;
    pushup(v), pushup(u);
}
inline void splay(int u, int k) {
    while (T[u].fa != k) {
        int v = T[u].fa, w = T[v].fa;
        if (w != k) {
            if ((T[v].s[1] == u) == (T[w].s[1] == v)) rotate(v);
            else rotate(u);
        }
        rotate(u);
    }
    if (!k) rt = u;
}
inline void ins(int val) {
    int u = rt, fa = 0;
    while (u && T[u].val != val) fa = u, u = T[u].s[val > T[u].val];
    if (T[u].val == val) T[u].cnt++, T[u].siz++;
    else {
        u = ++n;
        if (fa) T[fa].s[val > T[fa].val] = u;
        T[u].val = val, T[u].fa = fa, T[u].siz = T[u].cnt = 1;
    }
    splay(u, 0);
}
inline void del(int val) {
    int u = rt;
    while (u && T[u].val != val) u = T[u].s[val > T[u].val];
    if (!u) return;
    T[u].cnt--;
    splay(u, 0);
    if (T[u].cnt) return;
    if (!T[u].s[0]) rt = T[u].s[1], T[rt].fa = 0;
    else if (!T[u].s[1]) rt = T[u].s[0], T[rt].fa = 0;
    else {
        int fa = u; u = T[u].s[0];
        while (u) fa = u, u = T[u].s[1];
        splay(fa, rt);
        T[T[rt].s[1]].fa = fa, T[fa].s[1] = T[rt].s[1];
        rt = fa, T[rt].fa = 0, pushup(fa);
    }
}
inline int getrnk(int u, int k) {
    if (!u) return 1;
    if (k == T[u].val) return T[T[u].s[0]].siz + 1;
    else if (k < T[u].val) return getrnk(T[u].s[0], k);
    else return T[T[u].s[0]].siz + T[u].cnt + getrnk(T[u].s[1], k);
}
inline int getkth(int u, int k) {
    if (!u) return 0;
    int siz1 = T[T[u].s[0]].siz, siz2 = siz1 + T[u].cnt;
    if (siz1 < k && k <= siz2) return T[u].val;
    else if (k > siz2) return getkth(T[u].s[1], k - siz2);
    else return getkth(T[u].s[0], k);
}
inline int getpre(int k) {
    return getkth(rt, getrnk(rt, k) - 1);
}
inline int getsuf(int k) {
    return getkth(rt, getrnk(rt, k + 1));
}
int q;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> q;
    while (q--) {
        int op, x;
        cin >> op >> x;
        switch (op) {
            case 1: ins(x); break;
            case 2: del(x); break;
            case 3: cout << getrnk(rt, x) << endl; break;
            case 4: cout << getkth(rt, x) << endl; break;
            case 5: cout << getpre(x) << endl; break;
            default: cout << getsuf(x) << endl;
        }
    }
    fflush(stdout);
    return 0;
}