【模板】可持久化线段树 2(Persistent Segment Tree 2) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int lc = 0, rc = 0, cnt = 0;
};

vector<Node> tr;

int insert(int pre, int l, int r, int pos) {
    int u = (int)tr.size();
    tr.push_back(tr[pre]);
    tr[u].cnt++;
    if (l == r) return u;
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        int lc = insert(tr[pre].lc, l, mid, pos);
        tr[u].lc = lc;
    } else {
        int rc = insert(tr[pre].rc, mid + 1, r, pos);
        tr[u].rc = rc;
    }
    return u;
}

int query(int uL, int uR, int l, int r, int k) {
    while (l < r) {
        int mid = (l + r) >> 1;
        int leftCnt = tr[tr[uR].lc].cnt - tr[tr[uL].lc].cnt;
        if (k <= leftCnt) {
            uL = tr[uL].lc;
            uR = tr[uR].lc;
            r = mid;
        } else {
            k -= leftCnt;
            uL = tr[uL].rc;
            uR = tr[uR].rc;
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1), vals(n);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        vals[i - 1] = a[i];
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int V = (int)vals.size();
    tr.reserve(n * 22 + 5);
    tr.push_back(Node());
    vector<int> root(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int rk = (int)(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) + 1;
        root[i] = insert(root[i - 1], 1, V, rk);
    }
    for (int i = 0; i < m; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        int ansIdx = query(root[l - 1], root[r], 1, V, k);
        cout << vals[ansIdx - 1] << "\n";
    }
    return 0;
}