记录编号	600110	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	2.459 s
提交时间	2025-04-15 21:33:24	内存使用	23.03 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,q,m,cnt,tot;
int a[N],b[N];
struct node{
    int sum,l,r;
}t[N<<5];
int root[N];
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
void build(int &p,int l1,int r1){
    cnt++;
    p=cnt;
    if(l1==r1) return;
    int mid=(l1+r1)>>1;
    build(t[p].l,l1,mid);
    build(t[p].r,mid+1,r1);
    return;
}
void update(int p,int &now,int l1,int r1,int x){
    cnt++;
    now=cnt;
    t[now]=t[p];
    t[now].sum++;
    if(l1==r1) return;
    int mid=(l1+r1)>>1;
    if(x<=mid) update(t[p].l,t[now].l,l1,mid,x);
    else update(t[p].r,t[now].r,mid+1,r1,x);
    return;
}
int query(int p,int x,int l1,int r1,int k){
    if(l1==r1) return b[l1];
    int mid=(l1+r1)>>1;
    int ans=t[t[x].l].sum-t[t[p].l].sum;
    if(k<=ans) return query(t[p].l,t[x].l,l1,mid,k);
    else return query(t[p].r,t[x].r,mid+1,r1,k-ans);
}
int main(){
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    tot=unique(b+1,b+n+1)-b-1;
    build(root[0],1,tot);
    for(int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+tot+1,a[i])-b;
        update(root[i-1],root[i],1,tot,x);
    }
    int l,r,k,ans;
    for(int i=1;i<=m;i++){
        l=read();r=read();k=read();
        ans=query(root[l-1],root[r],1,tot,k);
        printf("%d\n",ans);
    }
    return 0;
}