洛谷【P3919】可持久化数组(可持久化线段树做法)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct node{
    int ls, rs, ans;
}tree[maxn << 5];
int n, m, tot, rt[maxn];

int Build(int l, int r){
    int root = ++tot;
    if(l == r){
        scanf("%d", &tree[root].ans);
        return root;
    }
    int mid = (l + r) >> 1;
    tree[root].ls = Build(l, mid);
    tree[root].rs = Build(mid + 1, r);
    return root;
}

int UpDate(int root, int l, int r, int vis, int pos){
    int c = ++tot;
    tree[c].ls = tree[root].ls;
    tree[c].rs = tree[root].rs;
    if(l == r){
        tree[c].ans = pos;
        return c;
    }
    int mid = (l + r) >> 1;
    if(vis <= mid) tree[c].ls = UpDate(tree[c].ls, l, mid, vis, pos);
    else tree[c].rs = UpDate(tree[c].rs, mid + 1, r, vis, pos);
    return c;
}

int Query(int root, int l, int r, int vis){
    if(l == r) return tree[root].ans;
    int mid = (l + r) >> 1;
    if(vis <= mid) return Query(tree[root].ls, l, mid, vis);
    else return Query(tree[root].rs, mid + 1, r, vis);
}

int main(){
    scanf("%d%d", &n, &m);
    rt[0] = Build(1, n);
    int k, op, vis, pos, cnt = 1;
    while(m--){
        scanf("%d%d", &k, &op);
        if(op == 1){
            scanf("%d%d", &vis, &pos);
            rt[cnt++] = UpDate(rt[k], 1, n, vis, pos);
        }
        else{
            scanf("%d", &vis);
            rt[cnt++] = rt[k];
            printf("%d\n", Query(rt[k], 1, n, vis));
        }
    }

    return 0;
}