https://www.luogu.com.cn/record/160905102

#include<bits/stdc++.h>
#define LL long long
#define val(x) tree[x].val
#define key(x) tree[x].key
#define sz(x) tree[x].sz
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define cnt(x) tree[x].cnt
using namespace std;
const LL N = 2e5 + 10;
struct Node { LL val, key, sz, ls, rs, cnt; } tree[N]; 
LL Q, rt, tot = 0; 
mt19937 Rand(time(0));
void upd(LL x) { sz(x) = sz(ls(x)) + sz(rs(x)) + cnt(x); }

void Rotate(LL &x, bool dir) {
    if (dir) {
        LL r  = rs(x);
        rs(x) = ls(r);
        ls(r) = x;
        upd(x); x = r; upd(x);
    } else {
        LL l = ls(x);
        ls(x) = rs(l);
        rs(l) = x;
        upd(x); x = l; upd(x);
    }
}

LL t;

void Insert(LL &p, LL x) {
    if (!p) {
        p = ++ tot;
        sz(p) = cnt(p) = 1; val(p) = x; key(p) = Rand();
        return ; 
    } else if (val(p) == x) {
        cnt(p) ++; sz(p) ++;
        return ;
    } else if (val(p) > x) {
        Insert(ls(p), x);
        if (key(ls(p)) > key(p))
            Rotate(p, 0);
        upd(p);
    } else if (val(p) < x) {
        Insert(rs(p), x);
        if (key(rs(p)) > key(p))
            Rotate(p, 1);
        upd(p);
    }
}

void Delete(LL &p, LL x) {
    if (!p) return ;
    if (val(p) > x) {
        Delete(ls(p), x);
        upd(p);
    } else if (val(p) < x) {
        Delete(rs(p), x);
        upd(p);
    } else if (val(p) == x) {
        cnt(p) --; -- t;
        if (cnt(p)) { upd(p); return ; }
        if (!ls(p) && !rs(p)) {
            p = 0;
            return ;
        }
        if (!rs(p) || key(ls(p)) < key(rs(p)))
            Rotate(p, 1), Delete(rs(p), x);
        else
            Rotate(p, 0), Delete(ls(p), x);
        upd(p);
    }
}

LL Rank(LL &p, LL x) {
    if (!p) return 1;
    if (x == val(p)) return sz(ls(p)) + 1;
    if (x < val(p)) return Rank(ls(p), x);
    return sz(ls(p)) + cnt(p) + Rank(rs(p), x);
}

LL Frank(LL &p, LL x) {
    if (!p) return 1145141919810ll;
    if (sz(ls(p)) >= x) return Frank(ls(p), x);
    if (sz(ls(p)) + cnt(p) >= x) return val(p);
    return Frank(rs(p), x - sz(ls(p)) - cnt(p));
}

LL Prev(LL x) {
    LL p = rt, ret = 1145141919810ll;
    while (p) {
        if (val(p) < x) ret = val(p), p = rs(p);
        else p = ls(p);
    }
    return ret;
}

LL Nxt(LL x) {
    LL p = rt, ret = -1145141919810ll;
    while (p) {
        if (val(p) > x) ret = val(p), p = ls(p);
        else p = rs(p);
    }
    return ret;
}


int main () {
  ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> Q;
    rt = 0;
    LL opt, x;
    while (Q --) {
        cin >> opt >> x;
        if (opt == 1) {
            Insert(rt, x);
            ++ t;
        } else if (opt == 2) {
            Delete(rt, x);
        } else if (opt == 3) {
            cout << Rank(rt, x) << "\n";
        } else if (opt == 4) {
            cout << Frank(rt, x) << "\n";
        } else if (opt == 5) {
            cout << Prev(x) << "\n";
        } else {
            cout << Nxt(x) << "\n";
        }
    }
    return 0;
}