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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 200010
using namespace std;
int n, m, a[maxn];
int b[maxn], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = a[i];
sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
int v, ch[2];
} T[maxn * 20]; int rt[maxn], top;
void update(int &i, int j, int l, int r, int k, int v) {
i = ++top; int m = l + r >> 1;
lc = Lc; rc = Rc; T[i].v = T[j].v + v;
if (l == r) return ;
if (k <= m) update(lc, Lc, l, m, k, v);
else update(rc, Rc, m + 1, r, k, v);
}
int query(int i, int j, int l, int r, int k) {
if (l == r) return l; int v = T[Lc].v - T[lc].v, m = l + r >> 1;
if (k <= v) return query(lc, Lc, l, m, k);
else return query(rc, Rc, m + 1, r, k - v);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
init_hash();
for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, cnt, a[i], 1);
for (int i = 1; i <= m; ++i) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
printf("%d\n", b[query(rt[x - 1], rt[y], 1, cnt, z)]);
}
return 0;
}
|