subtask1 AC,subtask2 WA+TLE

#include<iostream>
using namespace std;
#define ll long long
ll top;
int a[20000001];
int root[20000001];
struct tr{
	ll val,lson,rson;
};
tr tree[20000001];
int clone(ll p){
	tree[++top]=tree[p];
	return top;
}
int build(ll l,ll r,ll p){
	p=++top;
	if(l==r){
		tree[p].val=a[l];
		return top;
	}
	int mid=(l+r)>>1;
	tree[p].lson=build(l,mid,tree[p].lson);
	tree[p].rson=build(mid+1,r,tree[p].rson);
	return p;
}
int upd(ll l,ll r,ll p,ll x,ll val){
	p=clone(p);
	if(l==r){
		tree[p].val=val;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid) tree[p].lson=upd(l,mid,tree[p].lson,x,val);
		else tree[p].rson=upd(mid+1,r,tree[p].rson,x,val);
	}
	return p;
}
int query(int l,int r,int p,int x){
	if(l==r) return tree[p].val;
	int mid=(l+r)>>1;
	if(x<=mid) return query(l,mid,tree[p].lson,x);
	else return query(mid+1,r,tree[p].rson,x);
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,0);
	for(int i=1;i<=m;++i){
		int rt,mod33,x;
		cin>>rt>>mod33>>x;
		if(mod33==1){
			int y;
			cin>>y;
			root[i]=upd(1,n,root[rt],x,y);
		}
		else{
			cout<<query(1,n,root[rt],x)<<endl;
			root[i]=root[rt];
		}
	}
}