c++可持久化左偏树

可持久化左偏树是一种支持历史版本查询的数据结构，它可以在不破坏原有数据结构的基础上，对其进行修改和查询。下面是一个简单的C++可持久化左偏树的实现：

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

const int MAXN = 1e5 + 5;

struct Node {
    int val, ls, rs;
} t[MAXN * 40];

int n, m, cnt, root[MAXN];

int build(int l, int r) {
    int p = ++cnt;
    if (l == r) {
        t[p].val = 0;
        return p;
    }
    int mid = (l + r) >> 1;
    t[p].ls = build(l, mid);
    t[p].rs = build(mid + 1, r);
    return p;
}

int update(int pre, int l, int r, int x, int v) {
    int p = ++cnt;
    t[p] = t[pre];
    if (l == r) {
        t[p].val += v;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) t[p].ls = update(t[pre].ls, l, mid, x, v);
    else t[p].rs = update(t[pre].rs, mid + 1, r, x, v);
    return p;
}

int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int cnt = t[t[v].ls].val - t[t[u].ls].val;
    if (cnt >= k) return query(t[u].ls, t[v].ls, l, mid, k);
    else return query(t[u].rs, t[v].rs, mid + 1, r, k - cnt);
}

int main() {
    scanf("%d%d", &n, &m);
    root[0] = build(1, n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        root[i] = update(root[i - 1], 1, n, x, 1);
    }
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(root[l - 1], root[r], 1, n, k));
    }
    return 0;
}

上述代码实现了一个可持久化左偏树，支持区间第k小查询。其中，build函数用于建立一棵空树，update函数用于在原有版本的基础上插入一个新节点，query函数用于查询区间第k小。在主函数中，我们首先建立一棵空树，然后依次插入每个节点，最后进行m次区间查询。