rt

#include<bits/stdc++.h>
using namespace std;
int N,M,a[1000010],top=0,mp[10010],v;
struct dot{
	int val,ls,rs;
}tree[150000010];
void build(int l,int r,int id)
{
	if(l==r)
	{
		tree[id].val=a[l];
	}
	else
	{
		int mid=(l+r)>>1;
		tree[id].ls=++top;
		build(l,mid,top);
		tree[id].rs=++top;
		build(mid+1,r,top); 
	}
	return;
}
void find(int l,int r,int id,int x)
{
	if(l==r&&r==x)
	{
		printf("%d\n",tree[id].val);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		find(l,mid,tree[id].ls,x);
	}
	else
	{
		find(mid+1,r,tree[id].rs,x);
	}
	return;
}
void add(int l,int r,int id,int x,int g)
{
	if(l==r&&r==x)
	{
		tree[++top].val=g;
		tree[top].ls=tree[id].ls;
		tree[top].rs=tree[id].rs;
		return;
	}
	int mid=(l+r)>>1; 
	if(x<=mid)
	{
		add(l,mid,tree[id].ls,x,g);
		tree[++top].val=tree[id].val;
		tree[top].ls=top-1;
		tree[top].rs=tree[id].rs;
	}
	else
	{
		add(mid+1,r,tree[id].rs,x,g);
		tree[++top].val=tree[id].val;
		tree[top].ls=tree[id].ls;
		tree[top].rs=top-1;
	}
	return;
}
int main()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a[i]);
	}
	build(1,N,0);
	mp[0]=0;
	int i;
	for(i=1;i<=M;i++)
	{
		scanf("%d",&v);
		v=mp[v];
		short type;
		cin>>type;
		if(type==1)
		{
			int loc,value;
			scanf("%d%d",&loc,&value);
			add(1,N,v,loc,value);
			mp[i]=top;
		}
		else
		{
			int loc;
			scanf("%d",&loc);
			mp[i]=v;
			find(1,N,v,loc);
		}
	}
} 

记录： https://www.luogu.com.cn/record/192898555