python/TangDou/AcWing/BalanceTree/TODO/253_Tzy.cpp

#include <bits/stdc++.h>
using namespace std;

//替罪羊树，没有仔细研究

const int N = 100010;
const double alpha = 0.75; // 啊啊啊   double ！！

struct Scape_goat {
    int l, r;
    int val;
    int size; //  子树的大小（包括它自己）， 包括被打了删除标记的结点
    int exist;
    int fact;
} tr[N];
int idx;
int root;
int rec[N], cnt;

// 每次新建节点只管他自己，不需要管儿子们
void build(int &u, int val) {
    u = ++idx; // 开一个位置
    tr[u].val = val;
    tr[u].size = 1;
    tr[u].fact = 1;
    tr[u].exist = true;
}

/**
 *  重构条件 ：      当前节点的左子树或右子树的size  > 当前结点的大小 乘 一个平衡因子alpha (一般取0.75)
 *               或者以当前结点为根的子树中被删掉的点 > 该子树大小的 30%
 **/

bool isbalance(int u) {
    if (tr[tr[u].l].size > tr[u].size * alpha || tr[tr[u].r].size > tr[u].size * alpha) return false;
    if (tr[u].size - tr[u].fact > tr[u].size * 0.3) return false;
    return true;
}

/**
 * 重构： 将当前子树先中序遍历，  压扁，然后再拎起来
 **/

void inorder(int u) {
    if (!u) return;
    inorder(tr[u].l);
    if (tr[u].exist) rec[++cnt] = u;
    inorder(tr[u].r);
}

// pushup 的时候， 由于没有记录子节点到父节点的指针，  所以只能头递归
void pushup(int tmp, int op) {
    if (!tmp) return; //  整棵树都被删掉的情况
    if (tr[tmp].val > tr[op].val) {
        pushup(tr[tmp].l, op);
    } else
        pushup(tr[tmp].r, op);

    tr[tmp].size = tr[tr[tmp].l].size + tr[tr[tmp].r].size + 1;
    // fact 不需要修改
}

// l, r 指rec数组中存的子树中存在的结点
// u 是l ,r 这段区间所构成子树的根
void lift(int l, int r, int &u) {
    if (l == r) // 叶子结点
    {
        u = rec[l]; // 同样 传引用 将这个节点设置为他的父亲节点的儿子
        tr[u].l = tr[u].r = 0;
        tr[u].size = 1;
        tr[u].fact = 1;
        return;
    }
    int mid = (l + r) >> 1; // 找根
    // 因为 该树的定义为 左子树严格小于根， 所以 需要放置 连续mid左侧连续几个数相等的情况
    // 注意这儿的 l ,r mid 并不是结点，  rec[l, r, mid] 才是结点！！！
    while (mid > l and tr[rec[mid]].val == tr[rec[mid - 1]].val) mid--;
    u = rec[mid];
    if (mid == l)
        tr[u].l = 0;
    else
        lift(l, mid - 1, tr[u].l); // 注意递归两边的时候传mid - 1 与 mid + 1, 千万不能有mid,  否则可能自己的根是自己，导致递归炸掉

    lift(mid + 1, r, tr[u].r);
    tr[u].size = tr[u].fact = r - l + 1;
}

void rebuild(int &u) {
    cnt = 0;
    inorder(u);
    if (cnt == 0) { // 这颗子树整体都应该被删掉
        u = 0;      // 即他作为他的父节点的子结点变成了0， 传引用的好书
        return;
    }
    // 否则， 分治 拎起来
    lift(1, cnt, u);
}

/**
 * 检查并判断一棵树是否需要重构
 * 从根节点向当前被操作的结点一路判断，   找到第一个需要被重构的结点，并重构它
 * 注意顺序不能反， 如果反过来找，就可能重构好几次。
 **/

// tmp 是当前的结点， 从root 开始,  op 代指刚被操作过的结点
void check(int &tmp, int op) {
    if (tmp == op) return;
    if (!isbalance(tmp)) {
        rebuild(tmp);
        pushup(root, tmp); // 用子节点的size 更新父节点的size
        return;
    }
    if (tr[op].val < tr[tmp].val)
        check(tr[tmp].l, op);
    else
        check(tr[tmp].r, op);
}

// 左边放小于根的， 右边放 >= 根的
void insert(int &u, int val) // 上一层传来的参数是 tr[u].l 或 tr[u].r , 传引用相当于直接 修改 tr[u].l = xxx
{
    if (!u) {
        build(u, val);
        check(root, u);
        return;
    }
    tr[u].size++;
    tr[u].fact++;
    if (val < tr[u].val)
        insert(tr[u].l, val);
    else
        insert(tr[u].r, val);
}

// 懒惰删除， 只打标记不真删， 只减fact 不减 size
void del(int u, int val) {
    tr[u].fact--;
    if (tr[u].exist and tr[u].val == val) {
        tr[u].exist = false;
        check(root, u);
        return;
    }
    if (val < tr[u].val)
        del(tr[u].l, val);
    else
        del(tr[u].r, val);
}

// val 不一定存在
int get_rank_by_num(int val) {
    int tp = root;
    int rank = 1;
    while (tp) {
        if (val <= tr[tp].val)
            tp = tr[tp].l;
        else {
            rank += tr[tr[tp].l].fact + tr[tp].exist;
            tp = tr[tp].r;
        }
    }
    return rank;
}

int get_num_by_rank(int k) {
    int tp = root;
    while (tp) {
        if (tr[tr[tp].l].fact + tr[tp].exist == k and tr[tp].exist) break;
        if (tr[tr[tp].l].fact >= k) {
            tp = tr[tp].l;
        } else {
            k -= tr[tr[tp].l].fact + tr[tp].exist;
            tp = tr[tp].r;
        }
    }
    return tr[tp].val;
}

int get_pre(int val) // 前驱
{
    int k = get_rank_by_num(val);
    return get_num_by_rank(k - 1);
}
int get_next(int val) {
    // 注意不能  getnum(getrank(val) + 1)   防止 1224 这种情况，  排名x和x + 1可能是同一个数
    int k = get_rank_by_num(val + 1);
    return get_num_by_rank(k);
}

int main() {
    int n;
    scanf("%d", &n);
    int opt, x;
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1) {
            insert(root, x);
        } else if (opt == 2) {
            del(root, x);
        } else if (opt == 3) {
            printf("%d\n", get_rank_by_num(x));
        } else if (opt == 4) {
            printf("%d\n", get_num_by_rank(x));
        } else if (opt == 5) {
            printf("%d\n", get_pre(x));
        } else if (opt == 6) {
            printf("%d\n", get_next(x));
        }
    }

    return 0;
}