题目链接：https://www.luogu.org/problemnew/show/P3834

题目大意：如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。


主席树：

首先将值离散化之后，构建一颗值域线段树 
储存区间和,区间[l, r]表示
0版本的线段树是空树 
每次在值域上增加1就重构一颗线段树

很显然，任意两颗相邻线段树的值得和差为1 
而相同的区间内要么相等要么多1

那么，我们也很容易的可以推出，区间第k大可以通过第r版本和第（l-1）版本的线段树算出来 。

类型如：区间第k大元素，分治求解。
每次计算左儿子 
如果r的左儿子已经比(l-1)的左儿子多出来的和大于k 
那么在左儿子查找k大值 
否则则在右儿子上查找第(k-val)大值，其中，val是和的差


#include<bits/stdc++.h>

#define LL long Long
using namespace std;
const int maxn=2e5+10;

int L[maxn*20], R[maxn*20], sum[maxn*20];
int n, q, m ,cnt = 0;
int a[maxn], b[maxn], root[maxn];

#define mid (l+r)/2
int JS(int l, int r)
{
    int rt=++cnt;
    sum[rt]=0;
    if(l<r)
    {
        L[rt]=JS(l ,mid);
        R[rt]=JS(mid+1, r);
    }
    return rt;
}

int gx(int i, int l, int r, int x)
{
    int rt=++cnt;
    L[rt]=L[i], R[rt]=R[i], sum[rt]=sum[i]+1;//更新
    if(l<r)
    {
        if(x<=mid)
        {
            L[rt]=gx(L[i], l, mid, x);
        }
        else
        {
            R[rt]=gx(R[i], mid+1, r, x);
        }
    }
    return rt;
}

int cx(int u, int v, int l, int r, int k)
{
    if(l>=r)
    {
        return l;                        //找到区间
    }
    int x=sum[L[v]]-sum[L[u]];
    if(x>=k)
    {
        return cx(L[u], L[v], l, mid, k);//递归查找
    }
    else
    {
        return cx(R[u], R[v], mid+1, r, k-x);//放4递归查找
    }
}

int LSH()                               //离散化
{
    sort(b+1, b+1+n);
    m = unique(b+1, b+1+n)-b-1;
    for (int i = 1; i <= n; i ++)
    {
        a[i] = lower_bound(b+1, b+1+m, a[i])-b;
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    LSH();

    root[0] = JS(1, cnt);
    
    for(int i=1;i<=n;i++)
    {
        root[i]=gx(root[i-1], 1, m, a[i]);//更新
    }

    while (q --)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        int t = cx(root[x-1], root[y], 1, m, z);
        printf("%d\n", b[t]);
    }

    return 0;
}