记录编号	600117	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	2.609 s
提交时间	2025-04-15 21:56:50	内存使用	23.08 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],num[N],n,m,cnt=0,root[N];
int ql,qr,k;
struct Tree
{
    int l,r,sum;
}tree[N*4];
void build(int &o,int l,int r)
{
     o=++cnt;
     tree[o].sum=0;
     if(l==r) return ;
     int m=(l+r)/2;
     build(tree[o].l,l,m);
     build(tree[o].r,m+1,r);
}
void update(int p,int &o,int l,int r,int x)
{
     o=++cnt;
     tree[o]=tree[p];
     tree[o].sum++;
     if(l==r) return ;
     int m=(l+r)/2;
     if(x<=m)
       update(tree[p].l,tree[o].l,l,m,x);
     else
       update(tree[p].r,tree[o].r,m+1,r,x);
}
int query(int p,int o,int l,int r,int x)
{
     if(l==r) return l;
     int m=(l+r)/2;
     int ln=tree[tree[o].l].sum-tree[tree[p].l].sum;
     if(x<=ln) return query(tree[p].l,tree[o].l,l,m,x);
     else return query(tree[p].r,tree[o].r,m+1,r,x-ln);
}
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]);
      num[i]=a[i];
    }
    sort(num+1,num+n+1);
    int num_cnt=unique(num+1,num+n+1)-num-1; 
    build(root[0],1,num_cnt); 
    for(int i=1;i<=n;i++)
    {
      int x=lower_bound(num+1,num+num_cnt+1,a[i])-num;  //离散 

      update(root[i-1],root[i],1,num_cnt,x);
    }
    for(int i=1;i<=m;i++)
    {
      scanf("%d%d%d",&ql,&qr,&k);
      int x=query(root[ql-1],root[qr],1,num_cnt,k);
      printf("%d\n",num[x]);
    }
	return 0;
}