记录编号	457780	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.676 s
提交时间	2017-10-09 14:19:00	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define hash hash2
class Node{
public:
	int a,b;
	int sum;
	Node *l,*r;
};
Node* build(int l,int r){//default all 0
	Node *p=new Node();
	p->a=l,p->b=r,p->sum=0;
	if(l==r){
		p->l=p->r=NULL;
	}
	else{
		int mid=(l+r)/2;
		p->l=build(l,mid);
		p->r=build(mid+1,r);
	}
	return p;
}
Node* modify(Node *p0,int x,int k){
	if(x>p0->b||x<p0->a) return p0;
	Node* p=new Node(*p0);
	if(x<=p->a&&p->b<=x){
		p->sum+=k;
		return p;
	}
	p->sum+=k;
	int mid=(p->a+p->b)/2;
	if(x<=mid) p->l=modify(p->l,x,k);
	else p->r=modify(p->r,x,k);
	return p;
}
int query(Node *pl,Node *pr,int k){
	if(pl->a==pl->b) return pl->a;
	int t=pr->l->sum-pl->l->sum;
	if(k<=t) return query(pl->l,pr->l,k);
	else return query(pl->r,pr->r,k-t);
}
const int SIZEN=100010;
int N,Q;
int A[SIZEN],V[SIZEN];
int hash(int x){
	return lower_bound(V+1,V+1+N,x)-V;
}
Node *roots[SIZEN];
void work(void){
	roots[0]=build(1,N);
	for(int i=1;i<=N;i++) roots[i]=modify(roots[i-1],hash(A[i]),1);
	for(int i=1;i<=Q;i++){
		int x,y,k;scanf("%d%d%d",&x,&y,&k);
		printf("%d\n",V[query(roots[x-1],roots[y],k)]);
	}
}
void read(void){
	scanf("%d%d",&N,&Q);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]),V[i]=A[i];
	sort(V+1,V+1+N);
}
int main(){
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	//freopen("input.in","r",stdin);
	read();
	work();
	return 0;
}