前置知识：
权值线段树：相当于将线段树当成一个桶，其中的每一个点所代表的区间相当于一段值域。维护的值为这段值域中的一些信息。
可持久化概念：
可持久化实质上就是存储该数据结构所有的历史版本，以达到高效的处理某些信息的目的。

可持久化线段树：
假设当前线段树是这样的，修改如图的路径
图片说明
那么可持久化线段树会把这些点重新复制一遍，然后修改一些信息，所有新点里面只有改变的儿子变了，另外一个儿子还指向原来的节点。每一个版本线段树结构都是完全一样的，只不过信息不一样，因此对于每一个节点来说在不同版本的对应节点在原来树里面对应同一个位置。
由于可持久化线段树不能用堆的方式来存了，而应该用指针的方式来存：

struct 
{
    int l, r; // 表示左右子节点的下标
    int cnt; // 比方说线段树里存个当前区间中一共有多少个数
}

这种方式来存的时候，不需要存左右边界，而是在递归的时候把左右边界传下去。

空间复杂度分析：
如果有m次修改，每次修改都会有一个新的版本出来，某次修改时，哪些节点发生变化就建个新的节点，不变的不发生改变。每次最多改变logn个节点。

1.第K小数：题目链接
先考虑如何求总序列第k小
我们可以建立一颗权值线段树，每个点存储的信息为该值域区间存在的数的个数。
如何求整体第K小数？线段树本身是二叉树，所以在树本身里面就可以做二分。
比如[0,mid]有cnt个数，cnt >= k, 那么左边区间里有比k个数多的，递归左边，如果cnt < k, 递归右边。
问题转换到任意区间
从[1，R]可以用可持久化线段树的刚好加上前R个的版本，若同时有左右两边限制呢？用一个前缀和的思想，L,R版本的线段树上某个区间[l,r]的个数，就是R版本在[l,r]区间的个数减(L-1)版本在[l,r]区间的个数。
注意：由于值域很大，我们需要离散化一下。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int a[N];

vector<int> nums;

struct Node
{
    int l, r; //左儿子，右儿子 
    int cnt; // 信息，count 
}tr[N * 4 + N * 17]; //基础有N*4个节点，每次操作logn个，N次操作 

int root[N], idx;

int find(int x)    //离散化的查找函数 
{
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

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;
}

int insert(int p, int l, int r, int x) // p表示旧点，q表示新点，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;
} 

int query(int q, int p, 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[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt); // 左边已经有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());

    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]));    //和上一个版本的线段树比较,在find(a[i])位置上+1 

    while (m -- )
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]); // 同时递归两个版本 
    }

    return 0;
}