acwing算法提高之数据结构--可持久化数据结构

1 介绍

本专题用来记录可持久化数据结构相关的题目。

本专题主要讲如下两类数据结构的可持久化：

1. trie的可持久化
2. 线段树的可持久化，即主席树

可持久化的前提：本身的拓扑的结构不变。

解决什么类型的问题：可以保存下来数据结构的所有历史版本。
核心思想：只记录每一个版本与前一个版本不同的结点。

2 训练

题目1：256最大异或和

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 600010, M = N * 25;

int n, m;
int s[N];
int tr[M][2], max_id[M];
int root[N], idx;

void insert(int i, int k, int p, int q) {
    if (k < 0) {
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    if (p) tr[q][v^1] = tr[p][v^1];
    tr[q][v] = ++idx;
    insert(i, k-1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int root, int C, int L) {
    int p = root;
    for (int i = 23; i >= 0; --i) {
        int v = C >> i & 1;
        if (max_id[tr[p][v^1]] >= L) p = tr[p][v^1];
        else p = tr[p][v];
    }
    return C ^ s[max_id[p]];
}

int main() {
    scanf("%d%d", &n, &m);
    
    max_id[0] = -1;
    root[0] = ++idx;
    insert(0, 23, 0, root[0]);
    
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        s[i] = s[i-1] ^ x;
        root[i] = ++idx;
        insert(i, 23, root[i-1], root[i]);
    }
    
    char op[2];
    int l, r, x;
    while (m--) {
        scanf("%s", op);
        if (*op == 'A') {
            scanf("%d", &x);
            n++;
            s[n] = s[n-1] ^ x;
            root[n] = ++idx;
            insert(n, 23, root[n-1], root[n]);
        } else {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r-1], s[n]^x, l-1));
        }
    }
    return 0;
}
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

题目2：255第K小数

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010, M = 10010;

int n, m;
int a[N];
vector<int> nums;

struct Node {
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N], idx;

int find(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r) {
    int p = ++idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x) {
    int q = ++idx;
    tr[q] = tr[p];
    if (l == r) {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
    else tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k) {
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    root[0] = build(0, nums.size() - 1);
    
    for (int i = 1; i <= n; ++i) {
        root[i] = insert(root[i-1], 0, nums.size() - 1, find(a[i]));
    }
    
    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l-1], 0, nums.size() - 1, k)]);
    }
    
    return 0;
}
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