如题/kel/kel

#include <bits/stdc++.h>
using namespace std;

const int maxn=4e7+5;
int N,M,a[maxn],cnt,rr[maxn]/*存储版本i的根节点编号从0开始*/;

struct node
{
	int ls,rs,v;
}t[maxn];

int build(int l,int r)
{
	int id=++cnt;
	if(l==r) t[id].v=a[l];
	else
	{
		int mid=(l+r)/2;
		t[id].ls=build(l,mid);
		t[id].rs=build(mid+1,r);
	}
	return id;
}//记录左右儿子编号 

int neww(int x)
{
	cnt++,t[cnt]=t[x];
	return cnt;
}//新建节点 

int update(int now,int l,int r,int k,int v) 
{
	now=neww(now);
	if(l==r) t[now].v=v;
	else
	{
		int mid=(l+r)/2;
		if(k<=mid) t[now].ls=update(t[now].ls,l,mid,k,v);
		else t[now].rs=update(t[now].rs,mid+1,r,k,v);
	}
	return now;
}

int query(int now,int k,int l,int r)
{
	if(l==r) return t[now].v;
	else
	{
		int mid=(l+r)/2;
		if(k<=mid) return query(t[now].ls,k,l,mid);
		else return query(t[now].rs,k,mid+1,r);
	}
}

signed main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++) cin>>a[i];
	rr[0]=build(1,N);
	for(int i=1;i<=M;i++)
	{
		int opt,v,loc,value;
		cin>>v>>opt>>loc;
		if(opt==1) cin>>value,rr[i]=update(rr[v],1,N,loc,value);
		else cout<<query(rr[v],loc,1,N)<<endl;
	}
	return 0;
}