58 pts WA 7-12（替罪羊树）

#include <bits/stdc++.h>
#define N 100005
#define ALPHA 0.75
using namespace std;

int root, idx;
struct Node {
    int ls, rs;
    int val;
    int size; // 子树实际存储数值的结点数量
    int tot;  // 子树总节点数(包括删除的)
    int del;  // 标记是否被删除
} t[N];

void init_node(int u, int x) {
    t[u].ls = t[u].rs = 0;
    t[u].val = x;
    t[u].size = t[u].tot = 1;
    t[u].del = 1;
}

bool not_balance(int u) {
    return max(t[t[u].ls].tot, t[t[u].rs].tot) > ALPHA * t[u].tot;
}

vector<int> nodes;
void collect_nodes(int u) {
    if (!u) return;
    collect_nodes(t[u].ls);
    if (t[u].del) nodes.push_back(u);
    collect_nodes(t[u].rs);
}

void build(int l, int r, int &u) {
    if (l > r) {
        u = 0;
        return;
    }
    int mid = (l + r) >> 1;
    u = nodes[mid];
    build(l, mid - 1, t[u].ls);
    build(mid + 1, r, t[u].rs);
    t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;
    t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}

void rebuild(int &u) {
    nodes.clear();
    collect_nodes(u);
    build(0, nodes.size() - 1, u);
}

void insert(int &u, int x) {
    if (!u) {
        u = ++idx;
        init_node(u, x);
        return;
    }
    t[u].size++;
    t[u].tot++;
    if (x <= t[u].val) insert(t[u].ls, x);
    else insert(t[u].rs, x);
    if (not_balance(u)) rebuild(u);
}

int rank1(int u, int x) {
    if (!u) return 0;
    if (x <= t[u].val) return rank1(t[u].ls, x);
    return t[t[u].ls].size + t[u].del + rank1(t[u].rs, x);
}

void del_k(int &u, int k) {
    t[u].size--;
    int left_size = t[t[u].ls].size;
    if (t[u].del && k == left_size + 1) {
        t[u].del = 0;
        return;
    }
    if (k <= left_size + t[u].del) del_k(t[u].ls, k);
    else del_k(t[u].rs, k - left_size - t[u].del);
}

void del(int x) {
    int k = rank1(root, x) + 1;
    del_k(root, k);
    if (t[root].tot * ALPHA > t[root].size) rebuild(root);
}

int kth(int u, int k) {
    int left_size = t[t[u].ls].size;
    if (k <= left_size) return kth(t[u].ls, k);
    if (k == left_size + 1 && t[u].del) return t[u].val;
    return kth(t[u].rs, k - left_size - t[u].del);
}

int pre(int u, int x) {
    if (!u) return INT_MIN;
    if (t[u].val >= x) return pre(t[u].ls, x);
    int res = pre(t[u].rs, x);
    return t[u].del ? max(t[u].val, res) : res;
}

int suc(int u, int x) {
    if (!u) return INT_MAX;
    if (t[u].val <= x) return suc(t[u].rs, x);
    int res = suc(t[u].ls, x);
    return t[u].del ? min(t[u].val, res) : res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    while (n--) {
        int opt, x;
        cin >> opt >> x;
        switch (opt) {
            case 1: insert(root, x); break;
            case 2: del(x); break;
            case 3: cout << rank1(root, x) + 1 << "\n"; break;
            case 4: cout << kth(root, x) << "\n"; break;
            case 5: cout << pre(root, x) << "\n"; break;
            case 6: cout << suc(root, x) << "\n"; break;
        }
    }
    return 0;
}