记录编号	582642	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.945 s
提交时间	2023-09-20 21:53:59	内存使用	42.05 MiB

#include <bits/stdc++.h> 
using namespace std;
//重打！可持续化线段树 
const int N = 1e5+10;
int n,m;
int a[N],c[N];
int root[N],tot;
struct made{
    int ls,rs;
    int dat;
}t[N<<5];
void build(int &x,int l,int r){
    x = ++tot;
    if(l == r)return;
    int mid = l + r >> 1;
    build(t[x].ls,l,mid);
    build(t[x].rs,mid+1,r);
}
void add(int la,int &now,int l,int r,int x){
    now = ++tot;
    t[now] = t[la];
    t[now].dat++;
    if(l == r)return;
    int mid = l + r >> 1;
    if(x <= mid)add(t[la].ls,t[now].ls,l,mid,x);
    else add(t[la].rs,t[now].rs,mid+1,r,x);
}
int ask(int la,int x,int l,int r,int k){
    if(l == r)return c[l];
    int mid = l + r >> 1;
    int ans = t[t[x].ls].dat - t[t[la].ls].dat;
    if(k <= ans)return ask(t[la].ls,t[x].ls,l,mid,k) ;
    else return ask(t[la].rs,t[x].rs,mid+1,r,k-ans);
}
int main(){
    freopen("kthnumber.in","r",stdin);
    freopen("kthnumber.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(root[0],1,cnt);
    for(int i = 1;i <= n;i++){
        int x = lower_bound(c+1,c+1+cnt,a[i]) - c;
        add(root[i-1],root[i],1,cnt,x);
    }
    for(int i = 1;i <= m;i++){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",ask(root[l-1],root[r],1,cnt,k));
    }
    
    
    return 0;
    
}