1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

// 本代码中所有数据均按从下标 1 开始存放

// 主席树中的线段树结点，sum 表示此区间内元素个数
struct node {
	int sum, l, r;
} hjt[MAXN*40];

int a[MAXN], sorted[MAXN], num;	// sorted: 离散化后的数组 num: 离散化后的数组长度
int root[MAXN], cnt;	// root: 主席树中用来保存每棵线段树树根的数组 cnt: 线段树结点数（用于数组方式动态开点）

// 查找离散化之后的下标
int GetIdx(int v) {
	return lower_bound(sorted+1, sorted+1+num, v) - sorted;
}

// 初始化
void Init() {
	cnt = 0;
}

// 创建结点
inline int CreateNode(int sum, int l, int r) {
	int idx = ++cnt;
	hjt[idx].sum = sum;
	hjt[idx].l = l;
	hjt[idx].r = r;

	return idx;
}

// 新建一棵线段树，只沿更新路径新建出较上个版本有修改的结点
// 调用参数
// root: 插入后新生成的线段树的根结点会赋值到 root 中存储
// pre_rt: 上一棵线段树的根
// pos: 本次要插入的数在线段树中的位置
// l, r: 递归参数。默认填写 1, num
void Insert(int &root, int pre_rt, int pos, int l, int r) {
	// 动态创建结点，直接根据上一个版本复制对应的结点，sum+1
	root = CreateNode(hjt[pre_rt].sum+1, hjt[pre_rt].l, hjt[pre_rt].r);
	if(l == r) return;
	int m = (l+r) >> 1;
	if(pos <= m)
		Insert(hjt[root].l, hjt[pre_rt].l, pos, l, m);
	else Insert(hjt[root].r, hjt[pre_rt].r, pos, m+1, r);
}

// 本函数适用于查询区间 [l, r] 中的第 k 小。通常需要自行变通
// 调用参数
// s, e: 要查询区间所需的两个线段树的根，如要查询区间 [l, r]，则传入 root[l-1], root[r]
// k: 要查询区间第几小
// l, r: 递归参数。默认填写 1, num
int Query(int s, int e, int k, int l, int r) {
	if(l == r) return l;
	int m = (l+r) >> 1;
	int sum = hjt[hjt[e].l].sum - hjt[hjt[s].l].sum;	// 计算左子树的元素数量
	if(k <= sum)	// 如果 k <= sum，则 k 在左子树，否则在右子树
		return Query(hjt[s].l, hjt[e].l, k, l, m);
	else return Query(hjt[s].r, hjt[e].r, k-sum, m+1, r);
}

int main(int argc, char const *argv[]) {
	int n, m, l, r, k;
	while(~ scanf("%d %d", &n, &m)) {
		Init();
		for(int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			sorted[i] = a[i];
		}
		sort(sorted+1, sorted+1+n);	// 按值排序
		num = unique(sorted+1, sorted+1+n) - (sorted+1);	// 去重，返回去重后的元素数量
		for(int i=1; i<=n; ++i) {	// 按顺序插入，建立 n 棵权值线段树
			Insert(root[i], root[i-1], GetIdx(a[i]), 1, num);
		}
		while(m--) {
			scanf("%d %d %d", &l, &r, &k);
			printf("%d\n", sorted[Query(root[l-1], root[r], k, 1, num)]);
		}
	}
	
	return 0;
}