我发现了新的平衡树？？？！

前导

这也算是 Treap 的一个变体吧。借鉴了树的重心的思想。
我把这棵树叫做 BFT，即 Brute_Force Tree，暴力树。
小蒟蒻不会高级算法，如果已经有了类似的树，请各位尽管d我。

介绍

这种新的平衡树没有随机键值，而是通过子树大小来实现平衡操作。容易发现，如果这棵树的每一个节点都是其所在子树的重心，那么这棵树的深度一定是 \(\log(n)\) 的。所以，如果以这棵树的某个节点的两个儿子为根的两棵子树中有一棵的大小大于该节点为根的子树大小的一半，那么就旋转。代码中使用了 balance() 函数来实现这种操作。
删除节点、查找前驱、后继、排名同Treap。在这些函数的末尾应当调用 balance() 来保证平衡性。

复杂度

\(n\log(n)\)。开 O2 在 LibreOJ 上跑了 100ms，洛谷 165ms。
跑起来速度和 Treap 差不多，但是更好写，更好理解。

代码

放进 LibreOJ 里格式化了一下。

#include "iostream"
using namespace std;
#define inf 100010
#define maxn 1e8
struct node {
    int l, r, v, cnt, sum;
} bf[inf];
int top, n, rt;
template<typename T>inline bool read(T &x_) {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }

    x_ = x * f;
    return 1;
}
template<typename T, typename ...Args>inline bool read(T &a, Args &...args) {
    return read(a) && read(args...);
}
void print_(int x) {
    if (x >= 10)
        print_(x / 10);
    putchar(x % 10 + '0');
}
void print(int x) {
    if(x<0)x=-x,putchar('-');
    print_(x);
    putchar('\n');
}
void pushup(int x) {
    bf[x].sum = bf[bf[x].l].sum + bf[bf[x].r].sum + bf[x].cnt;
}
int newnode(int x) {
    bf[++top].v = x;
    bf[top].cnt = bf[top].sum = 1;
    return top;
}
void zig(int &p) { //右旋
    int q = bf[p].l;
    bf[p].l = bf[q].r, bf[q].r = p, p = q;
    pushup(bf[p].r), pushup(p);
}
void zag(int &p) { //左旋
    int q = bf[p].r;
    bf[p].r = bf[q].l;
    bf[q].l = p;
    p = q;
    pushup(bf[p].l), pushup(p);
}
void bdtree() {
    newnode(-maxn), newnode(maxn);
    rt = 1;
    bf[1].r = 2;
    pushup(rt);
}
void balance(int &p) {
    if (!p)
        return;

    pushup(p);

    if (bf[bf[p].l].sum > bf[p].sum / 2)
        zig(p);
    else if (bf[bf[p].r].sum > bf[p].sum / 2)
        zag(p);
}
void insert(int &p, int v) {
    if (p == 0)
        p = newnode(v);
    else if (bf[p].v == v)
        bf[p].cnt++;
    else if (bf[p].v > v)
        insert(bf[p].l, v);
    else
        insert(bf[p].r, v);

    balance(p);
}
void delnode(int &p, int v) {
    if (p == 0)
        return;

    if (bf[p].v == v) {
        if (bf[p].cnt > 1)
            bf[p].cnt--;
        else if (bf[p].l || bf[p].r) {
            if (!bf[p].r)
                zig(p), delnode(bf[p].r, v);
            else
                zag(p), delnode(bf[p].l, v);
        } else
            return p = 0, void();
    } else if (bf[p].v > v)
        delnode(bf[p].l, v);
    else
        delnode(bf[p].r, v);

    balance(p);
}
int getrk(int p, int v) {
    if (p == 0)
        return 0;

    if (bf[p].v == v)
        return bf[bf[p].l].sum + 1;

    if (bf[p].v > v)
        return getrk(bf[p].l, v);

    return getrk(bf[p].r, v) + bf[bf[p].l].sum + bf[p].cnt;
}
int gettg(int p, int rk) {
    if (p == 0)
        return maxn;

    if (bf[bf[p].l].sum >= rk)
        return gettg(bf[p].l, rk);

    if (bf[bf[p].l].sum + bf[p].cnt >= rk)
        return bf[p].v;

    return gettg(bf[p].r, rk - bf[bf[p].l].sum - bf[p].cnt);
}
int getpr(int p, int v) {
    if (p == 0)
        return -maxn;

    if (bf[p].v >= v)
        return getpr(bf[p].l, v);

    return max(getpr(bf[p].r, v), bf[p].v);
}
int getsu(int p, int v) {
    if (p == 0)
        return maxn;

    if (bf[p].v <= v)
        return getsu(bf[p].r, v);

    return min(getsu(bf[p].l, v), bf[p].v);
}
int main() {
    read(n);
    bdtree();

    for (int i = 1, opt, x; i <= n; i++) {
        read(opt, x);
        if (opt == 1)
            insert(rt, x);
        else if (opt == 2)
            delnode(rt, x);
        else if (opt == 3)
            print(getrk(rt, x) - 1);
        else if (opt == 4)
            print(gettg(rt, x + 1));
        else if (opt == 5)
            print(getpr(rt, x));
        else if (opt == 6)
            print(getsu(rt, x));
    }

    return 0;
}