分析

• 这是一个超级经典的题目。这是一个静态问题（原数组在操作的过程中不会发生变化）。可以使用以下方法求解：

（1）归并树，时间复杂度：$O(n \times log^3(n))$；

（2）划分树，时间复杂度：$O(n \times log(n))$，空间复杂度：$O(n \times log(n))$；只能解决这一个问题。不是支持区间第k小数的修改。

（3）树套树，时间复杂度：$O(n \times log^2(n))$，空间复杂度：$O(n \times log(n))$；这里使用线段树套平衡树，线段树中的每个节点是一个平衡树，平衡树中维护的是一个区间的有序序列。该数据结构的好处是支持区间第k小数的修改。

（4）可持久化线段树（主席树），时间复杂度：$O(n \times log(n))$，空间复杂度：$O(n \times log(n))$； 不是支持区间第k小数的修改。

• 本题选择（4）的方法解决。步骤如下：

（1）保序离散化；

（2）在离散化后的数值上建立线段树，维护每个区间中一共有多少个数（区间右边代表的数大于区间左边的）；

• 求所有数据的第k小数：

• 假设输入数据存储在数组a中，a[1]存储第一个数据，现在求a[L~R]之间的第k小数，应该怎么处理呢？刚开始root[0]表示没有插入任何数据的线段树，即第0个版本，插入第k个数后的线段树的根节点存储在root[i]中，即第i个版本；

• 求a[L~R]之间的第k小数，我们可以找到第R个版本的线段树根节点root[R]，如果此时在root[R]中查找第k小的数，查找的结果是前R个数中第k小的数。

• 我们需要考虑左边界L，对于每个版本的线段树，结构都是完全一样的，只不过存储的信息不同；类似于前缀和的思想，我们考虑root[L-1]，如果该版本的某个区间[left, right]中元素个数为cnt2个，root[R]对应区间[left, right]中元素个数为cnt1个，则cnt1-cnt2表示的就是第L个数到第R个数中在区间[left, right]中出现的数的次数。

• 最后考虑线段树应该开多大的空间，本题中最多有$N=10^5$个数据，每次插入一个数据就会记录一个版本的信息，会增加一条长度为$\lceil N \rceil=17$个路径，因此需要的空间大小是$N \times 4 + N \times 17$。

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

using namespace std;

const int N = 100010;

int n, m;  // 序列长度、询问个数
int a[N];  // 序列
vector<int> nums;  // 保序离散化数组

struct Node {
    int l, r;  // 当前节点的左右儿子的下标
    int cnt;  // 数据范围在[nums[l], nums[r]]的数据的个数
} tr[N * 4 + N * 17];

int root[N], idx;

// 返回数据x离散化后对应的下标
int find(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

// l: 区间左端点, r: 区间右端点
// 返回区间为[l, r]的线段树的根节点
int build(int l, int r) {

    int p = ++idx;  // 为当前节点分配节点

    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);

    return p;
}

// p: 上一个版本的线段树的根节点
// l、r: 线段树某个节点对应区间左端点和右端点
// x: 单点修改线段树中第x个数
// 返回新版本线段树的根节点
int insert(int p, int l, int r, int x) {

    int q = ++idx;

    tr[q] = tr[p];
    if (l == r) {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;

    return q;
}

// 返回版本(p, q]之间第k小的版本
// 当前遍历到的线段树对应的区间为[l, r]
int query(int p, int q, int l, int r, int k) {

    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;  // 左孩子数据个数
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }

    // 保序离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    // 没有插入任何数据对应版本0
    root[0] = build(0, nums.size() - 1);

    // 建立各个版本的线段树
    for (int i = 1; i <= n; i++) 
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));

    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)]);
    }

    return 0;
}