[BZOJ4399]魔法少女LJJ代码

以下是一份使用Treap实现的C++代码，仅供参考。

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

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;

int n, m;
int root, cnt;

struct Node {
    int val, key;
    int size;
    int ch[2];
} tr[MAXN];

inline int new_node(int val) {
    tr[++cnt].val = val;
    tr[cnt].key = rand();
    tr[cnt].size = 1;
    return cnt;
}

inline void pushup(int p) {
    tr[p].size = 1 + tr[tr[p].ch[0]].size + tr[tr[p].ch[1]].size;
}

inline void split(int p, int k, int &x, int &y) {
    if (!p) {
        x = y = 0;
        return;
    }
    if (tr[p].val <= k) {
        x = p;
        split(tr[p].ch[1], k, tr[p].ch[1], y);
    } else {
        y = p;
        split(tr[p].ch[0], k, x, tr[p].ch[0]);
    }
    pushup(p);
}

inline int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].key < tr[y].key) {
        tr[x].ch[1] = merge(tr[x].ch[1], y);
        pushup(x);
        return x;
    } else {
        tr[y].ch[0] = merge(x, tr[y].ch[0]);
        pushup(y);
        return y;
    }
}

inline void insert(int val) {
    int x, y;
    split(root, val, x, y);
    root = merge(merge(x, new_node(val)), y);
}

inline void remove(int val) {
    int x, y, z;
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(tr[y].ch[0], tr[y].ch[1]);
    root = merge(merge(x, y), z);
}

inline int kth(int k) {
    int p = root;
    while (p) {
        if (tr[tr[p].ch[0]].size >= k) {
            p = tr[p].ch[0];
        } else if (tr[tr[p].ch[0]].size + 1 == k) {
            return tr[p].val;
        } else {
            k -= tr[tr[p].ch[0]].size + 1;
            p = tr[p].ch[1];
        }
    }
    return -1;
}

inline int query_min() {
    int p = root;
    int res = INF;
    while (p) {
        res = min(res, tr[p].val);
        p = tr[p].ch[0];
    }
    return res;
}

int main() {
    srand(time(NULL));
    scanf("%d%d", &n, &m);
    for (int i = 1, opt, x; i <= n; ++i) {
        scanf("%d%d", &opt, &x);
        if (opt == 1) {
            insert(x);
        } else {
            remove(tr[cnt].val);
        }
    }
    printf("%d\n", query_min());
    while (m--) {
        int k;
        scanf("%d", &k);
        printf("%d\n", kth(k));
    }
    return 0;
}

代码实现中使用了一个结构体 `Node` 来表示平衡树的每一个节点。其中 `val` 表示节点存储的值，`key` 表示随机生成的优先级，`size` 表示以该节点为根的子树大小，`ch[0]` 和 `ch[1]` 分别表示左右儿子的下标。接下来就是一些经典的平衡树操作，例如 `split` 和 `merge` 用于分裂和合并平衡树，`insert` 和 `remove` 用于插入和删除节点，`kth` 和 `query_min` 用于查询平衡树中第 $k$ 小的数和最小值。