记录编号	559333	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3537.[POJ 2104]第k小的数	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.329 s
提交时间	2021-03-01 20:37:13	内存使用	20.63 MiB

/*
struct node{
}
queue<node>q;
int x,y;
node u;
u.p = x;
u.q = y;
q.push(u);

node u = q.front();
q.pop();
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005 << 5;
int l[maxn],r[maxn],sum[maxn];
int rt[maxn];
int num = 0;
int n,m,a[maxn >> 5],c[maxn >> 5];
void build(int &i,int l1,int r1) {
    i = ++ num;
    if(l1 == r1) {
        return ;
    }
    int mid = l1 + r1 >> 1;
    build(l[i] , l1 , mid);
    build(r[i] , mid + 1 , r1);
    return ;
}
void update(int& i,int pre,int l1,int r1,int k) {
    i = ++ num;
    l[i] = l[pre];
    r[i] = r[pre];
    sum[i] = sum[pre] + 1;
    if(l1 == r1)return ;
    int mid = l1 + r1 >> 1;
    if(k <= mid)update(l[i] , l[pre] , l1 , mid , k);
    else update(r[i] , r[pre] , mid + 1 , r1 , k);
    return ;
}
int query(int i,int pre,int l1,int r1,int k) {
    if(l1 >= r1)return c[l1];
    int x = sum[l[i]] - sum[l[pre]];
    int mid = l1 + r1 >> 1;
    if(x >= k)return query(l[i] , l[pre] , l1 , mid , k);
    else return query(r[i] , r[pre] , mid + 1 , r1 , k - x);
}
int main() {
    freopen("knumber.in","r",stdin);
    freopen("knumber.out","w",stdout);
    scanf("%d%d",&n,&m);
    build(rt[0] , 1 , n);
    for(int i = 1;i <= n;++ i) {
        scanf("%d",&a[i]);
        c[i] = a[i];
    }
    sort(c + 1 , c + 1 + n);
    int cnt = unique(c + 1 , c + 1 + n) - c - 1;
    for(int i = 1;i <= n;++ i) {
        update(rt[i] , rt[i - 1] , 1 , cnt , lower_bound(c + 1 , c + 1 + cnt , a[i]) - c);
    }
    for(int i = 1;i <= m;++ i) {
        int L,R,k;
        scanf("%d%d%d",&L,&R,&k);
        printf("%d\n",query(rt[R] , rt[L - 1] , 1 , cnt , k));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}