题解 P2343 宝石管理系统

· · 题解

题目链接

发现没有用 01 Trie 解决的方法，所以来发一篇题解。

01 Trie 是平衡树的上位替代品，有常数小，码量小的优点。注意，当维护一个序列时，操作只包含求前驱，后继，第 k 小，第 k 大时，才能考虑用 01 Trie 来作为平衡树的替代品。

考虑这道题目，从高位向低位建树，每次节点被经过 cnt 就加一。查询第 n 大时，从根节点开始，如果向 1 连出的儿子节点 cnt 大于等于 n，那么就说明答案在这一位为 1，否则 n 需要减去 1 儿子节点的 cnt，并走向 0 儿子节点。

走到最低位时则返回答案，没有什么需要注意的。

#include <bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define pii pair<int, int>
#define ll long long
#define vi vector<int>
#define P 1e9+7917120411

using namespace std;

const int N = 1e5 + 10;

struct Trie {
    int ch[2], cnt;
}tr[N*33];

int idx, n, m, a[N];

void insert(int x) {
    int p = 0;
    R(i, 30, 0) {
        int &to = tr[p].ch[((x>>i)&1)];
        if(!to) to = ++idx;
        p = to;
        tr[p].cnt++;
    }
}

#define ls (tr[p].ch[0])
#define rs (tr[p].ch[1])

int query(int k) {
    int p = 0, ret = 0;
    R(i, 30, 0) {
        if(tr[rs].cnt >= k) p = rs, ret += (1<<i);
        else k -= tr[rs].cnt, p = ls;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    L(i, 1, n) cin >> a[i], insert(a[i]);
    L(i, 1, m) {
        int op, x; cin >> op >> x;
        if(op == 1) cout << query(x) << '\n';
        if(op == 2) insert(x);
    }
    return 0;
}