记录编号	593297	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	4.900 s
提交时间	2024-08-28 22:52:21	内存使用	42.22 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[200010],cnt,rt[200010],top,num;
vector<long long> v;
long long get(long long x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
struct abc{
	long long l;
	long long r;
	long long s;
}e[5000010];
long long js(long long l,long long r){
	long long x=++cnt;
	if(l==r){
	  return x;	
	}
	e[x].l=js(l,(l+r)/2);
	e[x].r=js((l+r)/2+1,r);
//	cout<<e[x].l<<" "<<e[x].r<<" "<<endl;
	return x;
}
long long cr(long long pre,long long l,long long r,long long v){
	long long x=++cnt;
	e[x].l=e[pre].l,e[x].r=e[pre].r,e[x].s=e[pre].s+1;
	if(l==r){
		return x; 
	}
	long long mid=(r+l)/2;
	if(v<=mid){
		e[x].l=cr(e[pre].l,l,mid,v);
	}
	else{
		e[x].r=cr(e[pre].r,mid+1,r,v);
	}
	return x;
}
long long ask(long long x,long long y,long long l,long long r,long long k){
    if(l>=r)return l;
    long long ans=e[e[y].l].s-e[e[x].l].s;
    
    if (ans>=k) return ask(e[x].l, e[y].l, l, (l+r)/2, k);
    else return ask(e[x].r, e[y].r, (r+l)/2+1, r, k-ans);
}
int main(){
	freopen("kthnumber.in","r",stdin);
    freopen("kthnumber.out","w",stdout);
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		v.push_back(a[i]);
	}
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
	num=get(v[v.size()-1]);
	rt[0]=js(1,num);
	for(long long i=1;i<=n;i++){
		rt[i]=cr(rt[i-1],1,num,get(a[i]));
	}
    while(m--){
        long long x,y,k;
        cin>>x>>y>>k;
        cout<<v[ask(rt[x-1],rt[y],1,num,k)-1]<<endl;
    }
	return 0;
}