题目描述

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

输入输出格式

输入格式：

 

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l, r, kl,r,k , 表示查询区间[l, r][l,r] 内的第k小值。

 

输出格式：

 

输出包含k行，每行1个正整数，依次表示每一次查询的结果

#include
     
      using namespace std;const int maxn = 100005*2;int a[maxn], d, p[maxn];struct Node{    int cnt;    Node *ls, *rs;    void up(){        cnt = ls->cnt + rs->cnt;    }}pool[maxn*32], *tail=pool, *root[maxn], *zero;void build(){    zero = ++tail;    zero->ls = zero->rs = zero;    zero->cnt = 0;    root[0] = zero;}Node * newnode(){    Node * nd = ++tail;    nd->ls = nd->rs = zero;    nd->cnt = 0;    return nd;}Node * modify(Node * nd, int pos, int del, int l = 1, int r = d){    Node * nnd = newnode();    if(l == r)nnd->cnt = nd->cnt + del;    else{        int m = (l + r) >> 1;        if(pos <= m){            nnd->rs = nd->rs;            nnd->ls = modify(nd->ls, pos, del, l, m);        }        else{            nnd->ls = nd->ls;            nnd->rs = modify(nd->rs, pos, del, m+1, r);        }        nnd->up();    }        return nnd;    }int query(Node *lnd, Node *rnd, int k, int l = 1, int r = d){    if(l == r)return a[l];    int m = (l + r) >> 1;    int lz = rnd->ls->cnt - lnd->ls->cnt;    if(lz>= k)return query(lnd->ls, rnd->ls, k, l, m);    else return query(lnd->rs, rnd->rs, k-lz, m+1, r);}int main(){    int n,q;    scanf("%d%d",&n,&q);    for(int i = 1; i <= n; i++)scanf("%d",&a[i]),p[i]=a[i];    sort(a+1, a+1+n);    d = unique(a+1, a+1+n) - a - 1;    build();    for(int i = 1; i <= n; i++){        int tt = lower_bound(a+1, a+1+d, p[i]) - a;        root[i] = modify(root[i-1], tt, 1);    }     while(q--){        int l, r, k;        scanf("%d%d%d",&l,&r,&k);        printf("%d\n",query(root[l-1], root[r], k));    }    }