= Vain学习(C/C++ acm算法 python Linux Golang)的个人网站 =

Home

可持久化数组

Posted on

可持久化数组

可持久化数组其实就是保存了历史版本的数组。
对于历史版本，我们需要开一个rt[ ]来保存，
当前版本的根节点，我们通过根节点的索引，可以，
找到当前版本的树中，所携带rt[0]-rt[i]这个区间，
的任意点的信息。

题目描述

如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作，
在某个历史版本上修改某一个位置上的值，
访问某个历史版本上的某一位置的值，
此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入格式

输入的第一行包含两个正整数 N, MN,M， 分别表示数组的长度和操作的个数。
第二行包含NN个整数，依次为初始状态下数组各位的值（依次为 ai，1≤i≤N）
接下来MM行每行包含3或4个整数，代表两种操作之一（ii为基于的历史版本号）：

  • 1:对于操作1，格式为v 1 loc value ，即为在版本v的基础上，将 loc位置的值修改为 value
    ​
  • 2:对于操作2，格式为v 1 loc ，即为在版本v的基础上，询问loc位置的值

输出格式

输出包含若干行，依次为每个操作2的结果。

输入输出样例

输入

10
1
2
3
4
5
6
7
8
9
10
11
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

输出

1
2
3
4
5
6
59
87
41
87
88
46

参考代码:

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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
const int inf = (1 << 30);
typedef long long ll;
const int maxn = 1e6 + 5;
struct node
{
    int ls, rs, w;
} tr[maxn * 32];
int a[maxn], rt[maxn], cnt;
void inser(int ver, int &now, int L, int R, int pos, int w)
{
    now = ++cnt;
    tr[now] = tr[ver];
    if (L == R)
    {
        tr[now].w = w;
        return;
    }
    int mid = L + R >> 1;
    if (mid >= pos)
        inser(tr[ver].ls, tr[now].ls, L, mid, pos, w);
    else
        inser(tr[ver].rs, tr[now].rs, mid + 1, R, pos, w);
}
int ask(int now, int L, int R, int pos)
{
    if (L == R)
        return tr[now].w;
    int mid = L + R >> 1;
    if (mid >= pos)
        return ask(tr[now].ls, L, mid, pos);
    else
        return ask(tr[now].rs, mid + 1, R, pos);
}
int main()
{
    int n, m, x;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &x), inser(rt[0], rt[0], 1, n, i, x);
    for (int i = 1; i <= m; i++)
    {
        int ba, op, pos, w;
        scanf("%d %d", &ba, &op);
        if (op == 1)
        {
            scanf("%d %d", &pos, &w);
            inser(rt[ba], rt[i], 1, n, pos, w);
        }
        else
        {
            scanf("%d", &pos);
            int ans = ask(rt[ba], 1, n, pos);
            printf("%d\n", ans);
            rt[i] = rt[ba];
        }
    }
}
  1. 1. 可持久化数组