P3919 mle求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1111111],rt[1001100],n,m,id;
struct node{
	ll ls,rs,dat;
}tree[50055000];
void build(ll &p,ll l,ll r){
	p=++id;
	if(l==r){
		tree[p].dat=a[l];
		return ;
	}
	ll mid=(l+r)/2;
	build(tree[p].ls,l,mid);
	build(tree[p].rs,mid+1,r);
}
void update(ll fa,ll &p,ll l,ll r,ll x, ll y){
	p=++id;
	tree[p]=tree[fa];
	if(l==r){
		tree[p].dat=y;
	}
	ll mid=(l+r)/2;
	if(x<=mid){
		update(tree[p].ls,tree[fa].ls,l,mid,x,y);
	}
	else{
		update(tree[p].rs,tree[fa].rs,mid+1,r,x,y);
	}
}
int ask(ll p,ll x,ll l,ll r){
	if(l==r){
		return tree[p].dat;
	}
	ll mid=(l+r)/2;
	if(x<=mid){
		return ask(tree[p].ls,x,l,mid);
	}
	else{
		return ask(tree[p].rs,x,mid+1,r);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	build(rt[0],1,n);
	for(int i=1;i<=m;++i){
		ll t,op,x,y;
		cin>>t>>op;
		if(op==1){
			cin>>x>>y;
			update(rt[t],rt[i],1,n,x,y);
		}
		else{
			cin>>x;
			cout<<ask(rt[t],x,1,n);
			rt[i]=rt[t];
		}
	}
	return 0;
}