蒟蒻是记录的每个节点的左右儿子，建树是像线段树一样建的，调了有点久了

#include<bits/stdc++.h>

using namespace std;
const int N = 2e6 + 10; 
int n,m;
int s[N * 8],a[N * 8],lson[N * 8],rson[N * 8],Root,Ver[N * 8];
int num = 0,cnt = 0;


inline int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w * s;
}

inline void build(int k,int l,int r) {
    if(l == r) {
        s[k] = a[l];
        return ;
    }
    int mid = l + r >> 1;
	lson[k] = k << 1;
    build(k << 1,l,mid); 
	rson[k] = k << 1 | 1;
    build(k << 1 | 1,mid + 1,r);
}
inline void modify(int k,int pos,int l,int r,int New,int val) {
    if(l == r) {
        s[New] = val;
        return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid) {
        ++cnt;
        lson[New] = cnt;
        rson[New] = rson[k];
        modify(lson[k],pos,l,mid,cnt,val);
    }
    else {
        ++cnt;
        lson[New] = lson[k];
        rson[New] = cnt;
        modify(rson[k],pos,mid + 1,r,cnt,val);
    }
}
inline int Ask(int k,int l,int r,int pos) {
    if(l == r) {
        return s[k];
    }
    int mid = l + r >> 1;
    if(pos <= mid) {
        return Ask(lson[k],l,mid,pos);
    }
    else return Ask(rson[k],mid + 1,r,pos);
}
int main() {
    n = read(),m = read();
    for(int i = 1;i <= n;i++) {
        a[i] = read();
    }
    build(1,1,n);
   	cnt = 2 * n - 1;
    Ver[0] = 1;
    for(int i = 1;i <= m;i++) {
        int Version,opt,pos,val;
        Version = read(),opt = read();
        switch(opt) {
            case 1:
            pos = read(),val = read();
            Ver[i] = ++cnt;
            modify(Ver[Version],pos,1,n,cnt,val);
            break;
            case 2:
            pos = read();
            Ver[i] = Ver[Version];
            printf("%d\n", Ask(Ver[Version],1,n,pos));
            break;
        }
    }
    
    return 0;
}