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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson (root << 1)
#define rson (root << 1 | 1)
const int N = 5e6 + 10;
int a[N], b[N];
int T[N], rs[N], ls[N], sum[N], cnt;
void build(int &root, int l, int r) {
root = ++cnt;
sum[root] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls[root], l, mid);
build(rs[root], mid + 1, r);
}
void update(int &root, int l, int r, int pre, int data) {
root = ++cnt;
ls[root] = ls[pre], rs[root] = rs[pre];
sum[root] = sum[pre] + 1;
if (l == r) return;
int mid = (l + r) >> 1;
if (data <= mid)
update(ls[root], l, mid, ls[pre], data);
else
update(rs[root], mid + 1, r, rs[pre], data);
}
int query(int s, int e, int l, int r, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int Sum = sum[ls[e]] - sum[ls[s]];
if (k <= Sum)
return query(ls[s], ls[e], l, mid, k);
else
return query(rs[s], rs[e], mid + 1, r, k - Sum);
}
int main() {
ios::sync_with_stdio(false);
int t, n, m, q, l, r, k;
cin >> t;
while (t--) {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - b - 1;
cnt = 0;
build(T[0], 1, m);
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
for (int i = 1; i <= n; i++) update(T[i], 1, m, T[i - 1], a[i]);
while (q--) {
cin >> l >> r >> k;
int ans = query(T[l-1],T[r],1,m,k);
cout<<b[ans]<<'\n';
}
}
return 0;
}
|
