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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct tree {
int l, r;
ll s;
} tr[N << 7];
int n, m, a[N], tot, root[N];
vector<int> v;
#define mid ((l + r) >> 1)
void build(int& p, int l, int r) {
p = ++tot;
if (l == r) {
tr[p].s = 1;
return;
}
build(tr[p].l, l, mid);
build(tr[p].r, mid + 1, r);
}
int clone(int p) {
tr[++tot] = tr[p];
tr[tot].s += 1;
return tot;
}
void modify(int& p, int l, int r, int pos) {
p = clone(p);
if (l == r) return;
if (pos <= mid) modify(tr[p].l, l, mid, pos);
else modify(tr[p].r, mid + 1, r, pos);
}
int query(int x, int y, int l, int r, int k) {
if (l == r) return l;
int kth = tr[tr[x].l].s - tr[tr[y].l].s;
if (kth >= k) return query(tr[x].l, tr[y].l, l, mid, k);
else return query(tr[x].r, tr[y].r, mid + 1, r, k - kth);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), v.push-back(a[i]);
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
int vn = v.size();
build(root[0], 1, vn);
for (int i = 1; i <= n; i++)
a[i] = lower-bound(v.begin(), v.end(), a[i]) - v.begin() + 1, modify(root[i] = root[i - 1], 1, vn, a[i]);
for (int i = 1; i <= m; i++) {
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", v[query(root[r], root[l - 1], 1, vn, k) - 1]);
}
}
|