好的，这道题是“可持久化权值线段树”最经典的应用，通常这种数据结构也被称为主席树 (Chairman Tree)。

解决这个问题的核心思想是利用线段树的可减性，将区间问题转化为前缀问题。

核心思路

1. 查询区间 [l, r] 内的第 k 小值，可以看作是： (前 r 个数的信息) - (前 l-1 个数的信息) = (第 l 到 r 个数的信息)

2. 我们如何表示“前 i 个数的信息”？我们可以为每个前缀 a[1...i] 建立一棵权值线段树。这棵权值线段树的节点 [L, R] 存储的是，在前 i 个数中，数值落在 [L, R] 区间内的数有多少个。

3. 如果为每个前缀 i=1, 2, ..., n 都独立建一棵完整的线段树，空间和时间开销都会是 O(N²)，无法接受。

4. 可持久化登场！我们发现，从“前 i-1 个数的权值线段树”到“前 i 个数的权值线段树”，仅仅是增加了一个数 a[i]。这意味着整棵树的结构大部分是相同的，只有从根节点到 a[i] 对应叶子节点的路径上，每个节点的计数值 count 会加 1。

5. 因此，我们不必为 i 重新建树。我们只需要新建路径上的 logN 个节点，而其他节点可以直接重用（指向）版本 i-1 的旧节点。这样，每次版本更新（插入一个数）的时间和空间复杂度都降到了 O(logN)。

算法步骤

1. 离散化 (Discretization)

• 原序列中 a_i 的值域很大（高达 10^9），我们不能直接以值为下标建立线段树。
• 但是，我们只关心这些数的大小关系，并且涉及到的不同数值最多只有 n 个。
• 做法：把所有 a_i 收集起来，去重，然后排序。得到一个有序的数组 b。原序列中的每个数 a_i 都可以用它在 b 中的排名（下标）来代替。
• 这样，值域就被压缩到了 [1, m]，其中 m 是不同数值的个数 (m <= n)。

2. 构建可持久化线段树 (主席树)

• 我们建立 n+1 棵线段树的根，root[0], root[1], ..., root[n]。
• root[0] 是一棵空树，所有节点的计数值都为 0。
• root[i] 是在 root[i-1] 的基础上，插入离散化后的 a[i] 的值而形成的新版本的树。
• insert 操作：
  • insert(old_version_node, value) 会返回一个 new_version_node。
  • 它会创建一个新节点，复制旧节点的信息。
  • 然后根据 value 决定是往左子树还是右子树递归插入。
  • 假设往左，那么它会递归调用 insert(old_version.left_child, value)，得到一个新的左孩子 new_left_child。
  • 它的右孩子则直接指向旧版本的右孩子 old_version.right_child。
  • 最后更新新节点的计数值 count。

3. 查询操作

• 要查询区间 [l, r] 内的第 k 小值。我们利用 root[r] 和 root[l-1] 这两棵树。
• 从两个根节点 root[r] 和 root[l-1] 同时开始向下遍历。
• 在当前节点，我们计算它左子树的计数值之差： count_diff = root[r].left.count - root[l-1].left.count。
• 这个 count_diff 的含义是：在 a[l...r] 这些数中，有多少个的数值是落在当前节点左子树所代表的值域范围内的。
• 判断：
  • 如果 k <= count_diff，说明第 k 小的数在左子树代表的值域范围内。我们继续向左子树走。
  • 如果 k > count_diff，说明第 k 小的数在右子树代表的值域范围内。我们更新 k = k - count_diff，然后向右子树走。
• 重复这个过程，直到到达叶子节点。这个叶子节点所代表的离散化后的值，就是我们要找的答案。最后，我们再通过离散化数组 b 把它映射回原始值。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 200005;

// 主席树的节点
struct Node {
    int l, r; // 左右子节点的编号
    int cnt;  // 该节点代表的值域区间内有多少个数
};

int n, m;
int a[MAXN];          // 原始数组
std::vector<int> b;   // 离散化用的数组

int root[MAXN];       // root[i] 存储版本i的根节点编号
Node tree[MAXN * 20]; // 节点池，空间要开够，大约 n*log(n)
int tot = 0;          // 节点池的指针

// 获取离散化后的排名
int get_id(int val) {
    return std::lower_bound(b.begin(), b.end(), val) - b.begin() + 1;
}

// 建立一棵空的初始线段树 (可以省略，在第一次insert时动态创建)
// 这里为了逻辑清晰，先建一个全0的root[0]
void build(int& cur, int l, int r) {
    cur = ++tot;
    tree[cur].cnt = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(tree[cur].l, l, mid);
    build(tree[cur].r, mid + 1, r);
}

// 插入操作，pre是上一个版本的根，cur是当前版本的根
void insert(int& cur, int pre, int l, int r, int pos) {
    cur = ++tot; // 创建新节点
    tree[cur] = tree[pre]; // 复制上一个版本的信息
    tree[cur].cnt++; // 计数值+1

    if (l == r) return;

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        // 要插入的值在左子树
        insert(tree[cur].l, tree[pre].l, l, mid, pos);
    } else {
        // 要插入的值在右子树
        insert(tree[cur].r, tree[pre].r, mid + 1, r, pos);
    }
}

// 查询操作
int query(int u, int v, int l, int r, int k) {
    if (l == r) {
        return l; // 到达叶子节点，返回离散化后的值
    }

    // 计算左子树在[l, r]区间内的数的个数差
    int count_diff = tree[tree[v].l].cnt - tree[tree[u].l].cnt;
    int mid = (l + r) >> 1;

    if (k <= count_diff) {
        // 第k小数在左子树
        return query(tree[u].l, tree[v].l, l, mid, k);
    } else {
        // 第k小数在右子树，注意k要减去左子树的数的个数
        return query(tree[u].r, tree[v].r, mid + 1, r, k - count_diff);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        b.push_back(a[i]);
    }

    // 离散化
    std::sort(b.begin(), b.end());
    b.erase(std::unique(b.begin(), b.end()), b.end());

    int b_size = b.size();

    // 建立n个版本的线段树
    // root[0]是空树，可以显式build一个，或者让它的左右儿子都是0即可
    // 我们这里采用动态开点，root[0]就是0
    root[0] = 0; 
    tree[0].l = tree[0].r = tree[0].cnt = 0;
    tot = 0;

    for (int i = 1; i <= n; ++i) {
        insert(root[i], root[i - 1], 1, b_size, get_id(a[i]));
    }

    // 处理查询
    for (int i = 0; i < m; ++i) {
        int l, r, k;
        std::cin >> l >> r >> k;
        // 在root[r]和root[l-1]两棵树上查询
        int rank = query(root[l - 1], root[r], 1, b_size, k);
        // 通过排名找到原始值并输出
        std::cout << b[rank - 1] << "\n";
    }

    return 0;
}

代码解读

1. Node Struct: 定义了线段树节点，l 和 r 存储的是左右子节点在 tree 数组中的下标，而不是指针。cnt 是核心，记录了该节点代表的值域区间内有多少个数。
2. 离散化: 将所有输入数值a[i]存入b，排序去重。get_id(val) 函数通过二分查找（lower_bound）得到一个数值 val 对应的排名。
3. 建树: root[i] 存储了第 i 个版本的根节点在 tree 数组里的下标。我们从一个空的 root[0] 开始，循环 n 次，每次基于 root[i-1] 插入 a[i] 的排名，生成新的根 root[i]。
4. insert: 这是可持久化的关键。cur = ++tot; 创建一个新节点。tree[cur] = tree[pre]; 这一步非常重要，它让新节点先继承了旧节点的所有信息（包括两个孩子），这样我们只需要修改要更新的那一个孩子就行了，另一个孩子指针就自动“复用”了旧版本的。
5. query: query(root[l-1], root[r], ...) 这就是利用前缀性质的地方。tree[tree[v].l].cnt - tree[tree[u].l].cnt 精确地计算出了 [l, r] 区间内，值落在左子树范围的数的个数。根据这个差值和 k 的大小关系，就可以决定下一步往左还是往右，时间复杂度为 O(logN)。
6. 空间: 每次插入会新建 logN 个节点，总共有 n 次插入。所以总节点数大约是 n * logn。为了保险起见，数组大小通常开到 N * 20 或 N * 30。