记录编号	460574	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.942 s
提交时间	2017-10-17 19:03:29	内存使用	222.66 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
int n,m;
int v[100005],num[100005];
int cnt,size;
int rt[100005],lch[20000005],rch[20000005],sum[20000005];
inline void update(int &x,int las,int pos,int l,int r){
	x=++cnt;
	lch[x]=lch[las];
	rch[x]=rch[las];
	sum[x]=sum[las]+1;
	if(l==r)
		return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(lch[x],lch[las],pos,l,mid);
	else
		update(rch[x],rch[las],pos,mid+1,r);
}
inline int query(int x,int y,int l,int r,int k){
	if(l==r)
		return l;
	int mid((l+r)>>1),cnt(sum[lch[y]]-sum[lch[x]]);
	if(k<=cnt)
		return query(lch[x],lch[y],l,mid,k);
	else
		return query(rch[x],rch[y],mid+1,r,k-cnt);
}
inline int gg(){
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		num[i]=v[i]=read();
	sort(num+1,num+n+1);
	size=unique(num+1,num+n+1)-num-1;
	for(int i=1;i<=n;++i){
		v[i]=lower_bound(num+1,num+size+1,v[i])-num;
		update(rt[i],rt[i-1],v[i],1,size);
	}
	while(m--){
		int x(read()),y(read()),k(read());
		printf("%d\n",num[query(rt[x-1],rt[y],1,size,k)]);
	}
	return 0;
}
int K(gg());
int main(){;}