【模板】主席树(可持久化线段树)


题目链接:
可持久化数组:Luogu P3919 【模板】可持久化数组(可持久化线段树/平衡树)
静态区间第$K$小:Luogu P3834 【模板】可持久化线段树1(主席树)

代码:

可持久化数组

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <cctype>
#include <algorithm>

void readInt(int &v) {
char ch;
bool flag = false;
v = 0;
while (!isdigit(ch = getchar()))
if (ch == '-')
flag = true;
do
v = v * 10 + ch - '0';
while (isdigit(ch = getchar()));
if (flag) v *= -1;
}

struct Node {
int val;
Node *lson, *rson;
Node(int v = 0, Node *ls = NULL, Node *rs = NULL) :
val(v), lson(ls), rson(rs) {}
};
typedef Node *Iterator;

int n, m;
Iterator root[1000005];
int a[1000005], cur_version;

void build(int l, int r, Iterator it) {
if (l == r) {
it->val = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, it->lson = new Node);
build(mid + 1, r, it->rson = new Node);
}

void modify_dfs(Iterator cur_it, Iterator prev_it, int pos, int v) {
int l = 1, r = n;
while (l != r) {
int mid = (l + r) >> 1;
if (pos <= mid)
r = mid,
cur_it->rson = prev_it->rson,
cur_it->lson = new Node,
cur_it = cur_it->lson,
prev_it = prev_it->lson;
else
l = mid + 1,
cur_it->lson = prev_it->lson,
cur_it->rson = new Node,
cur_it = cur_it->rson,
prev_it = prev_it->rson;
}
cur_it->val = v;
}

int query_dfs(Iterator it, int pos) {
int l = 1, r = n;
while (l != r) {
int mid = (l + r) >> 1;
if (pos <= mid)
r = mid,
it = it->lson;
else
l = mid + 1,
it = it->rson;
}
return it->val;
}

void modify(int version, int pos, int v) {
root[++cur_version] = new Node;
modify_dfs(root[cur_version], root[version], pos, v);
}

int query(int version, int pos) {
root[++cur_version] = root[version];
return query_dfs(root[cur_version], pos);
}

int main() {
readInt(n), readInt(m);
for (int i = 1; i <= n; ++i)
readInt(a[i]);
build(1, n, root[0] = new Node);
while (m--) {
int op, version, pos;
readInt(version), readInt(op), readInt(pos);
if (op == 1) {
int v;
readInt(v);
modify(version, pos, v);
} else {
printf("%d\n", query(version, pos));
}
}
return 0;
}

静态区间第$K$小

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
#include <iostream>
#include <algorithm>

struct STNode;
typedef STNode *iterator;

struct STNode {
int val;
iterator lson, rson;
STNode(int v) : val(v), lson(nullptr), rson(nullptr) {}
} *root[200005], *null;

int arr[200005], arr2[200005], hash[200005];
int n, m, maxv;

void modify(int l, int r, iterator pos, iterator prev, int val) {
if (l == r) {
pos->val = prev->val + 1;
return;
}
int mid = (l + r) >> 1;
if (val <= mid)
pos->rson = prev->rson,
pos->lson = new STNode(prev->lson->val + 1),
modify(l, mid, pos->lson, prev->lson, val);
else
pos->lson = prev->lson,
pos->rson = new STNode(prev->rson->val + 1),
modify(mid + 1, r, pos->rson, prev->rson, val);
}

int query(int l, int r, iterator pos, iterator prev, int k) {
if (l == r)
return l;
int mid = (l + r) >> 1, sum1 = prev->lson->val, sum2 = pos->lson->val;
if (sum1 + k <= sum2)
return query(l, mid, pos->lson, prev->lson, k);
else
return query(mid + 1, r, pos->rson, prev->rson, k - sum2 + sum1);
}

void init() {
null = new STNode(0);
null->lson = null->rson = null;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i)
std::cin >> arr[i], arr2[i] = arr[i];
std::sort(arr + 1, arr + n + 1);
int *ptr = std::unique(arr + 1, arr + n + 1);
for (int i = 1; i <= n; ++i)
hash[i] = std::lower_bound(arr + 1, ptr, arr2[i]) - arr,
maxv = std::max(maxv, hash[i]);
root[0] = null;
for (int i = 1; i <= n; ++i)
modify(1, maxv, root[i] = new STNode(i), root[i - 1], hash[i]);
}

int main() {
init();
int l, r, k;
while (m--)
std::cin >> l >> r >> k,
std::cout << arr[query(1, maxv, root[r], root[l - 1], k)] << std::endl;
return 0;
}

 评论