16pts。求调。

吧唧一口，满满奶香

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+55;
int n,m,a[maxn],tot,rt[maxn],v,loc,c,val;

struct tree{
	int l,r,val;
}tree[maxn*20];

void build(int &rot,int l,int r){
	rot=++tot;
	if(l==r){
		tree[rot].val=a[1];
		return ;
	}
	
	int mid=l+r>>1;
	build(tree[rot].l,l,mid);
	build(tree[rot].r,mid+1,r);
}

void clone(int &rot,int cl){
	rot=++tot;
	tree[rot]=tree[cl];
}

void update(int &rot,int l,int r,int cl,int loc,int val){
	clone(rot,cl);
	if(l==r){
		tree[rot].val=val;
		return;
	}
	
	int mid=l+r>>1;
	if(loc<=mid) update(tree[rot].l,l,mid,tree[cl].l,loc,val);
	if(loc>mid) update(tree[rot].r,mid+1,r,tree[cl].r,loc,val);
/*

tree[rot].val=tree[tree[rot],l].val+tree[tree[rot].r].val;
*/
}

int _find(int rot,int l,int r,int loc){
	if(l==r) return tree[rot].val;
	int mid=l+r>>1;
	if(loc<=mid) return _find(tree[rot].l,l,mid,loc);
	else return _find(tree[rot].r,mid+1,r,loc);
}

signed main(void){
	
	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++){
		cin>>v>>c>>loc;
		if(c==1){
			cin>>val;
			update(rt[i],1,n,rt[v],loc,val);
		}
		if(c==2){
			printf("%d\n",_find(rt[v],1,n,loc));
			rt[i]=rt[v];
		}
	}
	
	return 0;
}