记录编号	458109	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.934 s
提交时间	2017-10-10 10:15:45	内存使用	30.46 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
inline 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-48;c=getchar();}
	return x*f;
}
const int maxn=100010;
int n,m;
struct dd{//离散化 
	int x,id;
	inline bool operator <  (const dd & a)const {
		return x<a.x;
	}
}data[maxn];
int sz;
int rk[maxn],sum[maxn*25],lson[maxn*25],rson[maxn*25],gen[maxn];
inline void change(int shang,int &xin,int l,int r,int nl,int nr){
	xin=++sz;
	if(l>=nl&&r<=nr){
		sum[xin]=sum[shang]+1;
		return ;
	}
	int m=(l+r)>>1;
	lson[xin]=lson[shang];
	rson[xin]=rson[shang];
	if(m>=nl)change(lson[shang],lson[xin],l,m,nl,nr);
	if(m<nr)change(rson[shang],rson[xin],m+1,r,nl,nr);
	sum[xin]=sum[lson[xin]]+sum[rson[xin]];
}
inline int kth(int shang,int xin,int l,int r,int k){
	if(l==r)return l;
	int m=(l+r)>>1;
	int lsum=sum[lson[xin]]-sum[lson[shang]];
	if(k<=lsum)return kth(lson[shang],lson[xin],l,m,k);
	return kth(rson[shang],rson[xin],m+1,r,k-lsum);
}
int main(){
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++){
		data[i].x=read();
		data[i].id=i;
	}
	sort(data+1,data+n+1);
	for(int i=1;i<=n;i++)rk[data[i].id]=i;//离散化 
	for(int i=1;i<=n;i++){
		change(gen[i-1],gen[i],1,n,rk[i],rk[i]);
	}
	for(int i=1;i<=m;i++){
		int l=read(),r=read(),k=read();
		printf("%d\n",data[kth(gen[l-1],gen[r],1,n,k)].x);
	}
	return 0;
}