luogu P3919 【模板】可持久化数组（可持久化线段树/平衡树）

As you see

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>

inline int read () {
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c=='-')f=-1; c=getchar();}
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
    return x*f;
}
const int maxn = 1000007;
int n,m,a[maxn],tot = 0,root[maxn];
struct Chairman_Tree {
    int ch[2],num ;
} ;
Chairman_Tree t[maxn << 4];
#define lc t[x].ch[0]
#define rc t[x].ch[1]
void build(int & x,int l,int r) {
    x = ++ tot;
    if(l == r) {
        t[x].num = a[l];return ;
    }
    int mid = l + r >> 1;
    build(lc,l,mid); build(rc,mid+1,r);return ;
}

int query(int x,int l,int r,int pos) {
    if(l == r) return t[x].num;
    int mid = l + r >>1;
    if(pos <= mid) return query(lc,l,mid,pos);
    else return query(rc,mid+1,r,pos);
}

void modify(int pre,int &x,int l,int r,int pos,int w) {
    t[x = ++tot] = t[pre];
    if(l == r) {
        t[x].num = w;return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid) modify(t[pre].ch[0],lc,l,mid,pos,w);
    else modify(t[pre].ch[1],rc,mid + 1,r,pos,w);
}
int main () {
    n = read(),m = read(); 
    for(int i = 1;i <= n;++ i) a[i] = read();
    build(root[0],1,n);
    for(int T,op,a,b,i = 1;i <= m;++ i) {
        T = read(),op = read();
        if(op == 1) {
            a = read(),b = read();
            modify(root[T],root[i],1,n,a,b);
        }
        else {
            a = read(),root[i] = root[T];
            printf("%d
",query(root[T],1,n,a));
        }
    }
    return 0;
}