01trie写法

题目描述见原题普通平衡树

普通平衡树【01trie写法】

个人认为这个比treap好写，而且其实不是很难想，我看写其他题解的dalao们都没说这个方法就补充一下
主要就是trie的模板，这里对一些多出来的东西做一个解释
sum[p]从代码中可以直接看出来，就是表示插入数的时候经过这个结点的次数，其实我们稍微转换一下，也就是结点p的子结点的个数
那么我们继续阅读代码，rank(x)表示的是小于x的数的个数，key(x)表示第x个数
于是我们可以知道对于每条询问的表达方式了
1、insert(x, 1)
2、insert(x, -1)
3、rank(x) + 1因为rank(x)表示小于x的数的个数，加一就是x的位置了
4、key(x)
5、key(rank(x))翻译过来就是：名次i为小于x的数的个数，即i = rank(x)，然后key(i)就是小于x的最大值了
6、类似5，我们做一个简单的推理，首先最后的表达式应该式类似于key(rank(x))这样的形式的，然后需要查找的是大于x的最小值，也就是等价于先求小于等于x的数的个数，设为i然后求key(i + 1)即可，也就是key(rank(x + 1) + 1)
知道了这些后，我们就可以写代码啦，其实就是trie的板子，代码难度比treap低了许多，写起来比较舒服，缺点是比较吃空间
补充一下，因为输入有可能为负数，所以我们需要将所有数加上一个base，保证输入非负即可
如果还看不明白的可以试着手写一个trie来模拟一下，就会有所理解了。

#include <bits/stdc++.h>
using namespace std;
const int N = 3200100, base = 1e7;
struct trie{
    int nex[N][2], num = 1;
    int root = 1;
    int sum[N];
    void insert(int x, int t) {//很普通的插入
        int p = root;
        x += base;//保证输入非负
        for (int i = 31; ~i; i -- ) {
            int c = x >> i & 1;
            if (!nex[p][c]) nex[p][c] = ++ num;
            p = nex[p][c];
            sum[p] += t;//就是多了这句，含义已经给出
        }
    }
    int rank(int x) {
        x += base;
        int p = root;
        int res = 0;
        for (int i = 31; ~i; i -- ) {
            int c = x >> i & 1;
            if (c) res += sum[nex[p][0]];//大概说一下我的理解，当该位为1时，找其他的该位为0的数的个数，就是严格小于这个数的个数了
            p = nex[p][c];
        }
        return res;
    }
    int key(int x) {
        int p = root;
        int res = 0;
        for (int i = 31; ~i; i -- ) {
            if (x > sum[nex[p][0]]) res += (1 << i), x -= sum[nex[p][0]], p = nex[p][1];//类似rank函数中的理解
            else p = nex[p][0];
        }
        return res - base;//因为我们之前加过一个base，所以这里要减去
    }
} trie1;
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; cin >> n;
    while (n -- ) {
        int ops, x; cin >> ops >> x;
        if (ops == 1) trie1.insert(x, 1);
        if (ops == 2) trie1.insert(x, -1);
        if (ops == 3) cout << trie1.rank(x) + 1 << endl;
        if (ops == 4) cout << trie1.key(x) << endl;
        if (ops == 5) cout << trie1.key(trie1.rank(x)) << endl;
        if (ops == 6) cout << trie1.key(trie1.rank(x + 1) + 1) << endl;
    }
    return 0;
}