WA例，求调感激不尽

#include <bits/stdc++.h>
using namespace std;
struct node{
    int l,r,data;
}tree[1000010];
int n,m,top,cnt,a[1000005],root[1000005],size=1,x,y,k,z;
void biuld(int d,int l,int r){
    if(l==r){
        tree[d].data=a[l];
        return;
    }
    tree[d].l=++cnt;
    tree[d].r=++cnt;
    biuld(tree[d].l,l,l+r>>1);
    biuld(tree[d].r,(l+r>>1)+1,r);
}
int change(int pre,int l,int r){
    if(l==r){
        return l;
    }
    int d=++cnt;
    tree[d].data=z;
    tree[d].l=tree[pre].l;
    tree[d].r=tree[pre].r;
    int mid=(l+r)>>1;
    if(mid>k)tree[d].l=change(tree[pre].l,l,mid);
    else     tree[d].r=change(tree[pre].r,mid+1,r);
    return d;
}
int query(int d,int l,int r){
    if(l==r){
        return tree[d].data;
    }
    int mid=(l+r)>>1;
    if(mid>=k)return query(tree[d].l,l,mid);
    else     return query(tree[d].r,mid+1,r);
}
int main() {
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    biuld(0,1,n);
    while(size<=m){
        scanf("%d %d %d",&x,&y,&k);
        if(y==1){
            root[size++]=cnt+1;
            scanf("%d",&z);
            change(root[x],1,n);
        }else {
            root[size++]=++cnt;
            tree[cnt]=tree[root[x]];
            printf("%d\n",query(root[x],1,n));
        }
    }
    return 0;
}