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

还是用主席树来做（因为提到不同的版本），这时候的主席树不是以权值为下标的，就是普通的线段树，维护范围1~n，i存的是a[ ]中的数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6 + 10, M = N * 30;
 4 struct node {
 5     int ls, rs, val;
 6 }t[M];
 7 int n, m, a[N], rt[N], cnt;
 8 void build(int &i, int l, int r) {
 9     i = ++ cnt;
10     if (l == r) {t[i].val = a[l]; return ;}
11     int mid = (l + r) >> 1;
12     build(t[i].ls, l, mid), build(t[i].rs, mid + 1, r);
13 }
14 void ins(int &i, int j, int l, int r, int x, int v) {
15     i = ++ cnt;
16     t[i] = t[j];//复制
17     if (l == r) {t[i].val = v; return ;}
18     int mid = (l + r) >> 1;
19     if (x <= mid) ins(t[i].ls, t[j].ls, l, mid, x, v);
20     else ins(t[i].rs, t[j].rs, mid + 1, r, x, v); 
21 }
22 int query(int i, int l, int r, int x) {
23     if (l == r) return t[i].val;
24     int mid = (l + r) >> 1;
25     if (x <= mid) return query(t[i].ls, l, mid, x);
26     else return query(t[i].rs, mid + 1, r, x);
27 }
28 int main() {
29     scanf("%d %d", &n, &m);
30     for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
31     build(rt[0], 1, n);
32     for (int i = 1; i <= m; i ++) {
33         int pre, opt, x, v;
34         scanf("%d %d %d", &pre, &opt, &x);
35         if (opt == 1) {scanf("%d", &v); ins(rt[i], rt[pre], 1, n, x, v);}
36         if (opt == 2) {printf("%d\n", query(rt[pre], 1, n, x)); rt[i] = rt[pre];/*复制相同版本*/}
37     }
38     return 0;
39 }