在 mwh 大佬的指引下,我最近学习了主席树。

思想

主席树是一种特殊的线段树,能够存储线段树的历史版本,我们称这种性质叫做可持久化。

主席树的可持久化通过这样来实现:我们每次修改单个节点,必然只会经过 $log_2n​$ 条“线段”,对于这些线段,我们都新开节点来存储。显然对于每一次修改操作,根节点都会被新建。那么我们只要存储下来每一次修改说对应的根节点即可。空间占用 $O(n log n)​$

具体思路可参考https://www.luogu.org/blog/LonecharmRiver/zhu-xi-shu中的图片。

关于模板题

我们要维护静态区间第 k 小。可以先把数组离散化,比如:

1
2
3
离散化前 4 1 1 2 8 9 4 4 3
离散化后 4 1 1 2 5 6 4 4 3
离散数组 1 2 3 4 8 9

我们根据离散数组作为所维护的区间。第 i 棵树存储[1, i]内各数值出现的次数。

完整代码

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 200010, maxm = maxn * 21;
int n, m, tn, l, r, x;
int a[maxn], b[maxn];
int tot, hed[maxn], sum[maxm], lc[maxm], rc[maxm];

void build(int &u, int l, int r) {
u = ++tot;
if (l == r) return;
int mid = (l + r) >> 1;
build(lc[u], l, mid);
build(rc[u], mid + 1, r);
}

void modify(int &u, int f, int l, int r, int k) {
u = ++tot, sum[u] = sum[f] + 1;
if (l == r) return;
int mid = (l + r) >> 1;
if (k <= mid) modify(lc[u], lc[f], l, mid, k), rc[u] = rc[f];
else modify(rc[u], rc[f], mid + 1, r, k), lc[u] = lc[f];
}

int query(int p, int q, int l, int r, int k) {
if (l == r) return b[l];
int mid = (l + r) >> 1;
if (sum[lc[q]] - sum[lc[p]] >= k) return query(lc[p], lc[q], l, mid, k);
else return query(rc[p], rc[q], mid + 1, r, k + sum[lc[p]] - sum[lc[q]]);
}

int main() {

n = read(), m = read();
for (int i = 1; i <= n; i++)
b[i] = a[i] = read();
sort(b + 1, b + n + 1);
tn = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + tn + 1, a[i]) - b;
build(hed[0], 1, tn);
for (int i = 1; i <= n; i++)
modify(hed[i], hed[i - 1], 1, tn, a[i]);

while (m--) {
l = read(), r = read(), x = read();
printf("%d\n", query(hed[l - 1], hed[r], 1, tn, x));
}

return 0;
}

后续 & 参考资料

需要注意:

  1. 我们需要事先建一棵空树;
  2. 由于上一条,我们需要n + n log n的空间。

参考资料: