记录编号	364109	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	1.187 s
提交时间	2017-01-15 14:11:02	内存使用	40.37 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ls(x) (a[x].lc)
#define rs(x) (a[x].rc)
const int maxn=150000;
struct Node{
	int lc,rc,sum;
}a[maxn*22];
struct Date{
	int date,pos;
	bool operator < (const Date & a)const{
		return date<a.date;
	}
}b[maxn];
int n,m,cnt;
int rank[maxn],root[maxn];
void Insert(int x,int & rt,int l,int r){
	a[++cnt]=a[rt];rt=cnt;
	a[rt].sum++;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)Insert(x,ls(rt),l,mid);
	else Insert(x,rs(rt),mid+1,r);
}
int Query(int k,int pr,int rt,int l,int r){
	if(l==r)return l;
	int mid=(l+r)>>1;
	int num=a[ls(rt)].sum-a[ls(pr)].sum;
	if(num>=k)return Query(k,ls(pr),ls(rt),l,mid);
	else return Query(k-num,rs(pr),rs(rt),mid+1,r);
}
void Init();
int main(){
	freopen("kth.in","r",stdin);freopen("kth.out","w",stdout);
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i].date);
		b[i].pos=i;
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)rank[b[i].pos]=i;
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		Insert(rank[i],root[i],1,n);
	}
	for(int i=1;i<=m;i++){
		int s,t,k;scanf("%d%d%d",&s,&t,&k);
		printf("%d\n",b[Query(k,root[s-1],root[t],1,n)].date);
	}
}