|
|
|
|
|
##[$P3919$ 【模板】可持久化线段树 $1$（可持久化数组）](https://www.luogu.com.cn/problem/P3919)
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
如题，你需要维护这样的一个长度为 $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$值，此时，因为要修改的是节点值，也无法采用什么懒标记了，就是一路向下递归，找到节点为止，时间和空间上都还过得去。
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#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;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
