记录编号	558176	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.855 s
提交时间	2020-12-13 14:00:16	内存使用	23.75 MiB

//氵 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct node {
	int l,r,sum;
	node() {
		l = r = sum = 0;
	}
}tree[maxn * 20];                                 
int rt[maxn],n,m,a[maxn],b[maxn],res[maxn],num,cnt;
inline int BF(int* res,int l,int r,int x) {
	int mid;             
	while(l <= r) {
		mid = l + r >> 1;
		if(res[mid] == x)return mid;
		if(res[mid] < x)l = mid + 1;
		else r = mid - 1;
	}
	return l;
}
inline void build(int &i,int l,int r) {
	i = ++ num;
	int mid = l + r >> 1;
	if(l < r) {
		build(tree[i].l , l , mid);
		build(tree[i].r , mid + 1 , r);
		return ;
	}
	return ;
}
inline void update(int &i,int pre,int l,int r,int k) {
	i = ++ num;
	tree[i] = tree[pre];
	++ tree[i].sum;
	int mid = l + r >> 1;
	if(l < r) {
		if(k <= mid)update(tree[i].l , tree[pre].l , l , mid , k);
		else update(tree[i].r , tree[pre].r , mid + 1 , r , k);
		return ;
	}
	return ;
}
inline int query(int pre,int now,int l,int r,int k) {
	if(l >= r)return l;
	int x = tree[tree[now].l].sum - tree[tree[pre].l].sum;
	int mid = l + r >> 1;
	if(k <= x)return query(tree[pre].l , tree[now].l , l , mid , k);
	else return query(tree[pre].r , tree[now].r , mid + 1 , r , k - x);
	return 0;
}                                                                    
int main() {                                                    
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&a[i]);
		b[i] = a[i];
	}            
	sort(b + 1,b + 1 + n);
	for(int i = 1;i <= n;++ i) {
		if(b[i] != b[i - 1]) {                                                                   
			res[++ cnt] = b[i];
		}
	}    
	build(rt[0] , 1 , cnt);
	for(int i = 1;i <= n;++ i) { 
		update(rt[i] , rt[i - 1] , 1 , cnt , BF(res , 1 , cnt , a[i]));
	}
	for(int i = 1;i <= m;++ i) {
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",res[query(rt[l - 1] , rt[r] , 1 , cnt , k)]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}