记录编号	144419	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.415 s
提交时间	2014-12-23 09:25:45	内存使用	65.14 MiB

/****************************************\
* Author : hzoi_ztx
* Title  : [河南省队2012] 找第k小的数
* ALG    :
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;

inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#include <algorithm>

#define  maxn  1000010LL
#define  maxt  4000000LL

struct num { int val , pos , tim ; } a[maxn] ;
bool CmpV(const num& a , const num& b) {
	if (a.val == b.val) return a.tim < b.tim ;
	return a.val < b.val ;
}
bool CmpT(const num& a , const num& b) {
	return a.tim < b.tim ;
}

int root[maxn] = {0} ;
int left[maxt] = {0} , right[maxt] = {0} , size[maxt] = {0} , tot = 0;
int leaf[maxn] = {0} ;

void Build(int root , int L , int R) {
	if (L == R) return ;
	left[root] = ++tot , right[root] = ++tot ;
	int M = L+(R-L)/2 ;
	Build(left[root] , L , M) ;
	Build(right[root] , M+1 , R) ;
}

void Insert(int root1 , int root2 , int L , int R , int pos) {
	size[root2] = size[root1]+1 ;
	if (L == R) return ;
	int M = L+(R-L)/2 ;
	if (pos > M) {
		left[root2] = left[root1] ;
		right[root2] = ++tot ;
		Insert(right[root1] , right[root2] , M+1 , R , pos ) ;
	} else {
		left[root2] = ++tot ;
		right[root2] = right[root1] ;
		Insert(left[root1] , left[root2] , L , M , pos) ;
	}
}

void Query(int root1 , int root2 , int L , int R , int k) {
	if (L == R) { printf("%d\n", leaf[L] ) ; return ; }
	int M = L+(R-L)/2 , tmpk = size[left[root2]]-size[left[root1]] ;
	if (k > tmpk) Query(right[root1] , right[root2] , M+1 , R , k-tmpk) ;
	else Query(left[root1] , left[root2] , L , M , k) ;
}

int n , m , i , j , k ;
int main() {
	#define READ
	#ifdef  READ
		freopen("kth.in" ,"r",stdin ) ;
		freopen("kth.out","w",stdout) ;
	#endif
	read(n) , read(m) ; root[0] = ++tot ;
	Build(root[0] , 1 , n) ;
	for (i = 1 ; i <= n ; i ++ ) read(a[i].val) , a[i].tim = i ;
	std::sort(a+1 , a+n+1 , CmpV) ;
	for (i = 1 ; i <= n ; i ++ ) a[i].pos = i , leaf[i] = a[i].val ;
	std::sort(a+1 , a+n+1 , CmpT) ;
	for (i = 1 ; i <= n ; i ++ ) root[i] = ++tot , Insert(root[i-1] , root[i] , 1 , n , a[i].pos) ;
	while ( m -- ) {
		read(i) , read(j) , read(k) ;
		Query(root[i-1] , root[j] , 1 , n , k) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}