题意：不修改查询区间第K个数

思路：主席树入门题。

/** @Date    : 2016-12-16-19.37  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include 
    
      #define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+10;const double eps = 1e-8;struct yuu{    int ls, rs;    int sum;}tt[N * 20];//int tot = 0;int a[N], b[N];int rt[N * 20];int n, m, k, x, y, T, sq;void build(int l, int r, int &p){    p = ++tot;    tt[p].sum = 0;    if(l == r)        return ;    int mid = (l + r) >> 1;    build(l, mid, tt[p].ls);    build(mid + 1, r, tt[p].rs);}void updata(int l, int r, int pre, int &p, int v){    p = ++tot;    tt[p].ls = tt[pre].ls;    tt[p].rs = tt[pre].rs;    tt[p].sum = tt[pre].sum + 1;    if(l == r)        return ;    int mid = (l + r) >> 1;    if(v <= mid)        updata(l, mid, tt[pre].ls, tt[p].ls, v);    else        updata(mid + 1, r, tt[pre].rs, tt[p].rs, v);}int query(int l, int r, int pre, int nw, int s){    if(l == r)        return b[l];    int mid = (l + r) >> 1;    int q = tt[tt[nw].ls].sum - tt[tt[pre].ls].sum;    if(s <= q)        query(l, mid, tt[pre].ls, tt[nw].ls, s);    else query(mid + 1, r, tt[pre].rs, tt[nw].rs, s - q);}int main(){    scanf("%d", &T);    while(T--)    {        scanf("%d%d", &n, &m);        for(int i = 1; i <= n; i++)            scanf("%d", a + i), b[i] = a[i];        sort(b + 1, b + 1 + n);        sq = unique(b + 1, b + n + 1) - (b + 1);        tot = 0;        build(1, sq, rt[0]);        for(int i = 1; i <= n; i++)        {            int v = lower_bound(b + 1, b + 1 + sq, a[i]) - b;            a[i] = v;        }        for(int i = 1; i <= n; i++)            updata(1, sq, rt[i - 1], rt[i], a[i]);        while(m--)        {            scanf("%d%d%d", &x, &y, &k);            int ans = query(1, sq, rt[x - 1], rt[y], k);            printf("%d\n", ans);        }    }    return 0;}