P3919 【模板】可持久化线段树 1（可持久化数组）

\(P3919\) 【模板】可持久化线段树 \(1\)（可持久化数组）

一、题目描述

如题，你需要维护这样的一个长度为 \(N\) 的数组，支持如下几种操作:

• 在某个历史版本上修改某一个位置上的值

• 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作\(2\)，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从\(1\)开始编号，版本\(0\)表示初始状态数组）

输入格式
输入的第一行包含两个正整数 \(N, M\)，分别表示数组的长度和操作的个数。

第二行包含\(N\)个整数，依次为初始状态下数组各位的值（依次为 \(a_i\)，\(1≤i≤N\)）。

接下来\(M\)行每行包含\(3\)或\(4\)个整数，代表两种操作之一（\(i\)为基于的历史版本号）：

对于操作\(1\)，格式为\(v_i \ 1 \ {loc}_i \ {value}_i\) ，即为在版本\(v_i\) 的基础上，将 \(a_{{loc}_i}\)
​修改为 \({value}_i\)

对于操作\(2\)，格式为\(v_i \ 2 \ {loc}_i\)，即访问版本\(v_i\) 中的 \(a_{{loc}_i}\) 的值，生成一样版本的对象应为\(v_i\)

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

二、解题思路

用主席树做,每次比之前会多\(log\)个点，空间上还过得去。

每题有两个与前面模板不一样的地方：

• 需要在\(build\)时初始化\(0\)版本主席树，因为有初始值\(a[i]\)
• 原来的主席树，都是空的，然后不断的\(insert\)进来，我还以为只能这样，其实主席树和线段树是一样的，当然也可以有\(update\)等操作，这时，就需要扩展结构体\(Node\),增加一个\(v\)属性，代表某个节点的\(v\)值，此时，因为要修改的是节点值，也无法采用什么懒标记了，就是一路向下递归，找到节点为止，时间和空间上都还过得去。

三、实现代码

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;
const int N = 1000010;

struct Node {
    int l, r, v;
} tr[N << 5];
int root[N], idx;
int n, m, a[N];

//快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

// build的原因，是因为有初始值，版本0不是空的
void build(int &u, int l, int r) {
    u = ++idx;
    if (l == r) {
        tr[u].v = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(tr[u].l, l, mid);
    build(tr[u].r, mid + 1, r);
}

void update(int &u, int l, int r, int x, int v) {
    tr[++idx] = tr[u];
    u = idx;
    if (l == r) {
        tr[idx].v = v;
        return;
    }
    int mid = l + r >> 1;
    if (mid >= x)
        update(tr[u].l, l, mid, x, v);
    else
        update(tr[u].r, mid + 1, r, x, v);
}

int query(int u, int l, int r, int x) {
    if (l == r) return tr[u].v;
    int mid = l + r >> 1;
    if (mid >= x)
        return query(tr[u].l, l, mid, x);
    else
        return query(tr[u].r, mid + 1, r, x);
}
/*
答案：
59
87
41
87
88
46
*/
int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("P3919.in", "r", stdin);
#endif
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();

    //构建主席树,因为有初始化值a[i]
    build(root[0], 1, n);

    for (int i = 1; i <= m; i++) {
        int x = read(), op = read(), y = read();
        if (op == 1) {
            // op=1:修改 x这个版本,管辖范围[1,n],将a[y]的值，即y这个位置,修改为v
            int v = read();
            root[i] = root[x];
            update(root[i], 1, n, y, v);
        } else {
            // op=2：访问版本x中，y这个位置上的值
            root[i] = root[x];
            printf("%d\n", query(root[i], 1, n, y));
        }
    }
    return 0;
}