【信奥做题日记】打板子：平衡树

#include <bits/stdc++.h>

using  namespace  std;
typedef  long long ll;
#define ls t[id].son[0]
#define rs t[id].son[1]
const int maxn = 1e6 + 5;
struct point {
    int val, dat, size, cnt;
    int son[2];
    // 分别表示值，优先级，子树大小，包含的副本数，左右子节点
} t[maxn];
int k = 0, root;

int add(int v) {
    t[++k].val = v;
    t[k].dat = rand();
    t[k].size = 1;
    t[k].cnt = 1;
    return k;
}

void push_up(int id) {
    t[id].size = t[ls].size + t[rs].size + t[id].cnt;
    // 本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 + 本节点副本数
}

void rotate(int &id, int d) { // id是引用传递，d为旋转方向，0为左旋，1为右旋
    int u = t[id].son[d ^ 1];
    t[id].son[d ^ 1] = t[u].son[d];
    t[u].son[d] = id;
    id = u;
    push_up(t[id].son[d]);
    push_up(id);
    // 旋转以后size会改变，看图就会发现只更新自己和转上来的点，push_up一下,注意先子节点再父节点
    // 旋转实质是在满足BST的性质的基础上比较优先级，通过交换本节点和其某个叶子节点把链叉开成二叉形状，从而控制深度，可以看图理解一下
}

void put_into(int &id, int v) {
    if (!id) {
        id = add(v); // 如果以前没有这个节点就新建一个
        return;
    }
    if (v == t[id].val) {
        ++t[id].cnt;
    } else {
        int d = v < t[id].val ? 0 : 1; // d代表方向，按照BST的性质，小于本节点则向左，大于向右
        put_into(t[id].son[d], v);
        if (t[id].dat < t[t[id].son[d]].dat) {
            rotate(id, d ^ 1); // 与左节点交换右旋，与右节点交换左旋
        }
    }
    push_up(id); //现在更新一下本节点的信息
}

void detach(int &id, int v) {
    if (!id) {
        return; // 如果发现查不到这个节点，即该点不存在，直接返回
    }
    if (v == t[id].val) { // 如果检索到了这个值
        if (t[id].cnt > 1) {
            --t[id].cnt;
            push_up(id);
            return;
        } //若副本不止一个，减去一个就好
        if (ls || rs) { // 发现只有一个值，且有儿子节点,我们只能把值旋转到底部删除
            if (!rs || t[ls].dat > t[rs].dat) {
                // 当前点被移走之后，按照优先级，选择左右儿子中更大的补上来
                rotate(id, 1);
                detach(rs, v);
                // 右旋是与左儿子交换，当前点变成右节点；左旋则是与右儿子交换，当前点变为左节点
            } else {
                rotate(id, 0);
                detach(ls, v);
            }
            push_up(id);
        } else {
            id = 0; // 发现本节点是叶子节点，直接删除
        }
        return; // 这个return对应的是检索到值的所有情况
    }
    if (v < t[id].val) { //继续BST性质
        detach(ls, v);
    } else {
        detach(rs, v);
    }
    push_up(id);
}

int get_rank(int id, int v) {
    if (!id) {
        return 1; // 若查询值不存在，返回；因为最后要减一排除哨兵节点，想要结果为-1这里就返回0
    }
    if (v == t[id].val) {
        return t[ls].size + 1;
        // 查询到该值，由BST性质可知，该点左边值都比该点的值(查询值)小，故rank为左儿子大小 + 1
    } else if (v < t[id].val) {
        return get_rank(ls, v);
        // 发现需查询的点在该点左边，往左边递归查询
    } else {
        return t[ls].size + t[id].cnt + get_rank(rs, v);
        // 若查询值大于该点值。说明询问点在当前点的右侧，且此点的值都小于查询值，所以要加上cnt[id]
    }
}

int get_val(int id, int rank) {
    if (!id) {
        return 1e9; // 一直向右找找不到，说明是正无穷
    }
    if (rank <= t[ls].size) {
        return get_val(ls, rank); // 左边排名已经大于rank了，说明rank对应的值在左儿子那里
    } else if (rank <= t[ls].size + t[id].cnt) {
        return t[id].val; // 上一步排除了在左区间的情况，若是rank在左与当前节点中，则直接返回当前节点中区间的值
    } else {
        return get_val(rs, rank - t[ls].size - t[id].cnt);
        // 剩下只能在右区间找了，rank减去左区间大小和中区间，继续递归
    }

}

int get_pre(int v, int id) {
    int pre = 0; // 递归不好返回，以循环求解
    while (id) { // 查到节点不存在为止
        if (t[id].val < v) {
            pre = t[id].val;
            id = rs; // 满足当前节点比目标小，往当前节点的右侧寻找最优值
        } else {
            id = ls; // 无论是比目标节点大还是等于目标节点，都不满足前驱条件，应往更小处靠近
        }
    }
    return pre;
}

int get_next(int v, int id) {
    int next = 0;
    while (id) {
        if (t[id].val > v) {
            next = t[id].val;
            id = ls;
        } else {
            id = rs;
        }
    }
    return next;
}

void solve() {
    int n;
    root = add(-1e9);
    t[root].son[1] = add(1e9);
    push_up(root);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) {
            put_into(root, x);
        } else if (opt == 2) {
            detach(root, x);
        } else if (opt == 3) {
            cout << get_rank(root, x) - 1 << '\n';
        } else if (opt == 4) {
            cout << get_val(root, x + 1) << '\n';
        } else if (opt == 5) {
            cout << get_pre(x, root) << '\n';
        } else if (opt == 6) {
            cout << get_next(x, root) << '\n';
        }
    }
}

void best() {

}

int main() {

    solve();

//    best();

    return 0;
}