第二个WA了

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
using namespace std;
int top,a[1000660],n,m,rot[1000660];
struct node{
	int l,r,v;
}tree[20006660];
inline int read() {
	int f = 1, k = 0;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') 	f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k=k * 10 + c - '0',	c = getchar();
	return f * k;
}
inline int clone(int root){
	tree[++top]=tree[root];
	return top;
}
int build(int root,int l,int r){
	root=(++top);
	if(l==r){
		tree[root].v=a[l];
		return top;
	}
	tree[root].l=build(tree[root].l,l,mid);
	tree[root].r=build(tree[root].r,mid+1,r);
	return root;
}
int modify(int root,int l,int r,int x,int val){
	root=clone(root);
	if(l==r) tree[root].v=val;
	else{
		if(x<=mid) tree[root].l=modify(tree[root].l,l,mid,x,val);
		else tree[root].r=modify(tree[root].r,mid+1,r,x,val);
	}
	return root;
}
int query(int root,int l,int r,int x){
	if(l==r) return tree[root].v;
	else{
		if(x<=mid) return query(tree[root].l,l,mid,x);
		else return query(tree[root].r,mid+1,r,x);
	}		
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	rot[0]=build(0,1,n);
	for(int i=1;i<=m;i++){
		int rt,op,x;
		rt=read(),op=read(),x=read();
		if(op==1){
			int y;
			y=read();
			rot[i]=modify(rot[rt],1,n,x,y);
		}
		else{
			printf("%lld\n",query(rot[rt],1,n,x));
			rot[i]=rot[rt];
		}
	}
}