\(\text{luogu-3919}\)
如题，你需要维护这样的一个长度为 \(n\) 的数组，支持如下两种操作：
- 在某个历史版本上修改某一个位置上的值。
- 访问某个历史版本上的某一位置的值。
具体来说：
- 对于操作 \(1\)，格式为
v 1 p c，即为在版本 $ v $ 的基础上，将 $ a_{p} $ 修改为 \(c\)。 - 对于操作 \(2\)，格式为
v 2 p，即访问版本 $ v $ 中的 $ a_{p} $ 的值，注意：生成一样版本的对象应为 \(v\)。
每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 \(1\) 开始编号，版本 \(0\) 表示初始状态数组）。
对于操作 \(2\)，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。
\(1 \le n,m \le 10^5\)，\(-10^9 \le a_i, c \le 10^9\)。
可持久化数组（主席树）板子。
以下部分题解来自于 题解：P3919 【模板】可持久化线段树 1（可持久化数组） - 洛谷专栏。
一种简单，容易想到的暴力做法就是每一次创建一个新版本就复制一个新数组，时间和空间复杂度都是 \(\mathcal{O}(mn)\)（\(m\) 次操作，每次创建一个大小为 \(n\) 的数组，从原数组复制要进行 \(n\) 次操作）。本题 \(1 \le n,m \le 10^5\)，这种做法显然不可接受。
我们观察需要创建新版本的场景，可以发现每次最多只会修改一个数，有时甚至不会修改，这些不修改的数字如果每一次都复制的话代价太高了。很容易想到每一次只记录修改的部分。
我们可以使用一种叫做可持久化线段树的数据结构。（没学过线段树的请右转学习线段树。）
我们现在先将版本 \(0\) 到版本 \(2\) 的线段树单独画出来：
我们发现版本 \(0\) 和版本 \(1\) 是重复的，我们可以直接将这些节点合并（将第二颗树的根节点的儿子设成第一颗树的根节点的儿子）：
对于版本 \(2\)，它只修改了一个数，我们可以想到只记录根节点到修改部分的一条“链”，其余的按照上面的方法操作：
总结：先将版本 \(0\) 的树完整的记录下来，接着之后的版本只记录修改的部分。
现在我们考虑复杂度：
空间复杂度：版本 \(0\) 要记录所有的数，会有 \(2n-1\) 个节点。总共有 \(m\) 个版本。假设每一个版本都有修改，那么每一次都要记录长为 \(\lceil \log_2 n \rceil+1\) 的“链”，空间复杂度约为 \(\mathcal{O}(n+m\log_2 n)\)。在此题中 \(n\) 和 \(m\) 最大为 \(10^6\)，内存限制为 \(1\) GB，可以接受。
时间复杂度：建第一棵树复杂度为 \(\mathcal{O}(n)\)，后面每一次查找复杂度都是 \(\mathcal{O}(\log n)\) 的，合起来就是 \(\mathcal{O}(n+m \log n)\)。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000005long long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}struct node { long long l, r, w; } t[MAXN << 5];
long long n, m, rt[MAXN], np, cnt;long long build(long long l, long long r) {long long p = (++ cnt), mid = (l + r) >> 1;if(l == r) { t[p].w = read(); return p; }t[p].l = build(l, mid), t[p].r = build(mid + 1, r);return p;
}long long upd(long long x, long long k, long long l, long long r, long long v) {long long p = (++ cnt), mid = (l + r) >> 1;t[p].l = t[v].l, t[p].r = t[v].r;if(l == r) { t[p].w = k; return p; }if(x <= mid) t[p].l = upd(x, k, l, mid, t[v].l);else t[p].r = upd(x, k, mid + 1, r, t[v].r);return p;
}long long qry(long long x, long long l, long long r, long long p) {if(l == r) return t[p].w;long long mid = (l + r) >> 1;if(x <= mid) return qry(x, l, mid, t[p].l);return qry(x, mid + 1, r, t[p].r);
}int main() {n = read(), m = read(), rt[np ++] = build(1, n);while(m --) {long long v = read(), op = read(), x = read(), k;if(op == 1) k = read(), rt[np ++] = upd(x, k, 1, n, rt[v]);else cout << qry(x, 1, n, rt[np ++] = rt[v]) << "\n";}return 0;
}