WA了第二个点

#include<bits/stdc++.h>
#define ll long long
const int MAXN=1e6+16;
using namespace std;
int a[20*MAXN],n,m,cnt;
int root[MAXN];//每个历史版本的根节点 
struct tree{
	int l[20*MAXN],r[20*MAXN],val[20*MAXN];
}t;
void build(int &u,int l,int r){//版本为i 
	u=++cnt;
	if(l==r){
		t.val[u]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(t.l[u],l,mid);
	build(t.r[u],mid+1,r);
}
int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
void change(int &u,int v,int l,int r,int p,int val){
	u=++cnt;
	t.l[u]=t.l[v];
	t.r[u]=t.r[v];
	t.val[u]=t.val[v]; 
	if(l==r){
		t.val[u]=val;
		return ;
	}
	int mid=(r+l)>>1;
	if(p<=mid){
		change(t.l[u],t.l[v],l,mid,p,val);
	}
	else{
		change(t.r[u],t.r[v],mid+1,r,p,val);
	}
}
int query(int i,int l,int r,int q){
	    if(l==r)return t.val[i];
        int mid=(l+r)>>1;
        if(q<=mid)return query(t.l[i],l,mid,q);
        else return query(t.r[i],mid+1,r,q);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(root[0],1,n);
	for(int i=1;i<=m;i++){
		int pre=read();
		int opt=read();
		int x=read();
		if(opt==1){
			int v=read();
			change(root[i],root[pre],1,n,x,v);
		}
		if(opt==2){
			cout<<query(root[pre],1,n,x)<<endl;
			root[i]=root[pre];
		}
	}
} 
/*
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91
*/