替罪羊树 58 Pts WA7-12 玄关求优化

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

int root, idx;
struct Node {
    int ls, rs;
    int val;
    int tot; // 当前子树占用的空间，包括实际存储的结点和被删除的结点
    int size; // 子树实际存储数值的结点数量
    int del; // del = 1 表示这个结点存有数值
} 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) {
    double u_alpha = (double)t[u].size * ALPHA; // 计算不平衡率
    double max_size = (double)max(t[t[u].ls].size, t[t[u].rs].size);
    return max_size > u_alpha;
}

int order[N], cnt;
int tree_stack[N], top;
void in_order(int u) {
    if (!u) return; // 到达叶结点
    in_order(t[u].ls); // 先遍历左子树
    if (t[u].del) order[++cnt] = u; // 读取它
    else tree_stack[++top] = u; // 回收该结点，等到重新分配使用
    in_order(t[u].rs); // 再遍历右子树
}

void updata(int u) {
    t[u].size = t[t[u].ls].size + t[t[u].rs].size + t[u].del;
    t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}

void build(int l, int r, int &u) {
    int mid = (l + r) >> 1; // 新的根设为中点
    u = order[mid];
    if (l == r) { // 如果是叶子，重置后返回
        init_node(u, t[u].val);
        return;
    }
    if (l < mid) build(l, mid - 1, t[u].ls); // 重构左子树
    else t[u].ls = 0;
    if (mid < r) build(mid + 1, r, t[u].rs); // 重构右子树
    else t[u].rs = 0;
    updata(u);
}

// 重建
void rebuild(int &u) {
    cnt = 0;
    in_order(u); // 拍平摧毁
    if (cnt)
        build(1, cnt, u); // 拎起重建
    else u = 0; // 特判该子树为空
}

// 在子树 u 中插入结点 x
void insert(int &u, int x) {
    if (!u) { // 若结点为空，直接将x插入
        u = tree_stack[top--];
        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 == 0) return 0; // 空结点，返回 0
    if (x > t[u].val) {
        // 当前结点的值小于 x，加上左子树的大小和当前结点（如果未被删除）
        return t[t[u].ls].size + t[u].del + rank1(t[u].rs, x);
    } else {
        // 当前结点的值大于或等于 x，只递归左子树
        return rank1(t[u].ls, x);
    }
}

// 删除排名为 k 的树
void del_k(int u, int k) {
    t[u].size--;
    if (t[u].del && k == t[t[u].ls].size + 1) { // 如果当前结点未被删除，而且当前结点是第 k 小的元素
        t[u].del = 0; // 标记该结点为空（删除）
        return;
    }
    if (k <= t[t[u].ls].size + t[u].del) del_k(t[u].ls, k);
    else del_k(t[u].rs, k - t[t[u].ls].size - t[u].del);
}

// 删除结点 x
void del(int x) {
    int k = rank1(root, x) + 1;
    del_k(root, k);
    if (t[root].tot * ALPHA > t[root].size) rebuild(root); // 若子树上被删结点太多，则重构
}

// 查询排名为 k 的数
int kth(int u, int k) {
    if (k <= t[t[u].ls].size) return kth(t[u].ls, k);
    if (k == t[t[u].ls].size + 1 && t[u].del) return t[u].val;
    return kth(t[u].rs, k - t[t[u].ls].size - t[u].del);
}

// 查询 x 的前驱
int pre(int u, int x) {
    if (!u) return -1e9;
    if (t[u].val >= x) return pre(t[u].ls, x);
    return max(t[u].val, pre(t[u].rs, x));
}

// 查询 x 的后继
int suc(int u, int x) {
    if (!u) return 1e9;
    if (t[u].val <= x) return suc(t[u].rs, x);
    return min(t[u].val, suc(t[u].ls, x));
}

int main() {
    // 初始化 tree_stack
    for (int i = N - 1; i >= 1; i--) tree_stack[++top] = i;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) {
            insert(root, x);
        } else if (opt == 2) {
            del(x);
        } else if (opt == 3) {
            cout << rank1(root, x) + 1 << endl;
        } else if (opt == 4) {
            cout << kth(root, x) << endl;
        } else if (opt == 5) {
            cout << pre(root, x) << endl;
        } else if (opt == 6) {
            cout << suc(root, x) << endl;
        }
    }
    return 0;
}