记录编号	570314	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 2104]K-th Number	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.064 s
提交时间	2022-03-26 08:22:48	内存使用	13.40 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int n,m;
int a[maxn],c[maxn];
int rt[maxn],ls[maxn << 5],rs[maxn << 5],sum[maxn << 5],num;
void build(int& i,int l,int r) {
    i = ++ num;
    sum[i] = 0;
    if(l == r)return ;
    int mid = l + r >> 1;
    build(ls[i] , l , mid);
    build(rs[i] , mid + 1 , r);
    return ; 
}
void modify(int& i,int pre,int l,int r,int val) {
    i = ++ num;
    ls[i] = ls[pre];
    rs[i] = rs[pre];
    sum[i] = sum[pre] + 1;
    if(l == r)return ;
    int mid = l + r >> 1;
    if(val <= mid)modify(ls[i] , ls[pre] , l , mid , val);
    else modify(rs[i] , rs[pre] , mid + 1 , r , val);
    return ;
}
int query(int i,int pre,int l,int r,int k) {
    if(l == r)return c[l];
    int mid = l + r >> 1,x = sum[ls[i]] - sum[ls[pre]];
    if(x >= k)return query(ls[i] , ls[pre] , l , mid , k);
    return query(rs[i] , rs[pre] , mid + 1 , r , k - x);
}
int main() {
    freopen("knumber.in","r",stdin);
    freopen("knumber.out","w",stdout);
    scanf("%d%d",&n,&m);
    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;
    build(rt[0] , 1 , cnt);
    for(int i = 1;i <= n;++ i)modify(rt[i] , rt[i - 1] , 1 , cnt , lower_bound(c + 1 , c + 1 + cnt , a[i]) - c);
    while(m --) {
        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;
}