题面
首先看到题面，想到莫队
修改$O(n\sqrt n)$次，询问$O(n)$次
使用的数据结构支持插入删除，k小
为了平衡两部分复杂度，使用单点分块 插入$O(1)$询问$O(\sqrt n)$
复杂度$O(n\sqrt n)$ 假设n，m同阶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
using namespace std;
const int radio = 320;
int id[100010], n, m;
struct data {
int a[100010], sum[100010];
int sze;
inline void add(int x) {
if(x == 0) return;
a[x]++;
sum[id[x]]++;
}
inline void del(int x) {
if(x == 0) return;
a[x]--;
sum[id[x]]--;
}
inline int getk(int k) {
// printf("%d\n", sum[1]);
for(int i = 1; i <= sze; i++) {
if(sum[i] < k) k -= sum[i];
else {
for(int j = (i - 1) * radio + 1; ; j++) {
if(a[j] < k) k -= a[j];
else return j;
}
}
}
return -1;
}
inline void build() {
sze = (n + radio - 1) / radio;
for(int i = 1; i <= n; i++) id[i] = (i + radio - 1) / radio;
// for(int i = 1; i <= n; i++) printf("%d ", id[i]);
// puts("");
}
} dt;
int ans[100010];
struct query {
int l, r, k, x;
friend inline int operator < (const query &a, const query &b) {
return id[a.l] == id[b.l] ? id[a.l] & 1 ? a.r < b.r : a.r > b.r : a.l < b.l;
}
} q[100010];
int a[100010], buc[100010], b[100010];
inline void add(int x) {
dt.del(buc[x]);
dt.add(++buc[x]);
}
inline void del(int x) {
dt.del(buc[x]);
dt.add(--buc[x]);
}
int main() {
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++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
for(int i = 1; i <= m; i++) scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k), q[i].x = i;
dt.build();
sort(q + 1, q + 1 + m);
int nowl = 1, nowr = 0;
for(int i = 1; i <= m; i++) {
while(nowr < q[i].r) add(a[++nowr]);
while(nowl > q[i].l) add(a[--nowl]);
while(nowr > q[i].r) del(a[nowr--]);
while(nowl < q[i].l) del(a[nowl++]);
// printf("%d %d\n", nowl, nowr);
ans[q[i].x] = dt.getk(q[i].k);
}
for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}