还是用主席树来做（因为提到不同的版本），这时候的主席树不是以权值为下标的，就是普通的线段树 ， 维护范围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 { 5int ls, rs, val; 6 }t[M]; 7 int n, m, a[N], rt[N], cnt; 8 void build(int &i, int l, int r) { 9i = ++ cnt;10if (l == r) {t[i].val = a[l]; return ;}11int mid = (l + r) >> 1;12build(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) {15i = ++ cnt;16t[i] = t[j];//复制17if (l == r) {t[i].val = v; return ;}18int mid = (l + r) >> 1;19if (x <= mid) ins(t[i].ls, t[j].ls, l, mid, x, v);20else ins(t[i].rs, t[j].rs, mid + 1, r, x, v);21 }22 int query(int i, int l, int r, int x) {23if (l == r) return t[i].val;24int mid = (l + r) >> 1;25if (x <= mid) return query(t[i].ls, l, mid, x);26else return query(t[i].rs, mid + 1, r, x);27 }28 int main() {29scanf("%d %d", &n, &m);30for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);31build(rt[0], 1, n);32for (int i = 1; i <= m; i ++) {33int pre, opt, x, v;34scanf("%d %d %d", &pre, &opt, &x);35if (opt == 1) {scanf("%d", &v); ins(rt[i], rt[pre], 1, n, x, v);}36if (opt == 2) {printf("%d\n", query(rt[pre], 1, n, x)); rt[i] = rt[pre];/*复制相同版本*/}37}38return 0;39 }【可持久化数组 P3919 【模板】可持久化线段树 1】
推荐阅读
- P3402 可持久化并查集
- 欧莱雅小蜜罐面霜敏感肌可以用吗_欧莱雅小蜜罐面霜适合什么肤质
- VideoPipe可视化视频结构化框架开源了！
- 小米平板5pro可以插卡吗_小米平板5pro可以打电话吗
- ARC148游记
- MySQL用户也可以是个角色
- steam怎么退款（steam激活码可以退款吗)
- steam退款如何操作（steam捆绑包可以退款吗)
- steam游戏怎么申请退款理由（steam捆绑包可以退款吗)
- steam如何强制退款（steam上可以退款吗)