RT

大数据就炸了

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct tree{
	int l,r,lson,rson,val;
}t[24000001];
int a[1234657],cnt;
void build(int l,int r,int o)
{
//	cerr<<o<<" "<<l<<" "<<r<<endl;
	t[o].l=l;t[o].r=r;
	if(l==r)
	{
		cnt=max(cnt,o);
		t[o].val=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,o*2);
	build(mid+1,r,o*2+1);
	t[o].lson=o*2;
	t[o].rson=o*2+1;
}
void newn(int tl,int tr,int ls,int rs,int v)
{
	cnt++;
	t[cnt]={tl,tr,ls,rs,v};
}
void change(int x,int o,int v)
{
	if(t[o].l==t[o].r)
	{
		newn(t[o].l,t[o].r,0,0,v);
		return;
	}
	int mid=(t[o].l+t[o].r)/2;
	if(x>mid)
	{
		change(x,t[o].rson,v);
		newn(t[o].l,t[o].r,t[o].lson,cnt,0);
	}
	else
	{
		change(x,t[o].lson,v);
		newn(t[o].l,t[o].r,cnt,t[o].rson,0);
	}
}
int ask(int x,int o)
{
//	cerr<<o<<" ";
	if(t[o].l==t[o].r) 
	{
//		cerr<<o<<endl;
		return t[o].val;
	}
	int mid=(t[o].l+t[o].r)/2;
	if(x>mid) return ask(x,t[o].rson);
	else return ask(x,t[o].lson);
}
int n,m,i,j,rt[1919810],rtc,op,ver,loc,v;
signed main()
{
//	freopen("P3939_6.in","r",stdin);
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	build(1,n,1);
	rt[0]=1;
	for(i=1;i<=m;i++)
	{
//		cerr<<"o!\n";
		scanf("%lld%lld%lld",&ver,&op,&loc);
		if(op==1)
		{
			scanf("%lld",&v);
			change(loc,rt[ver],v);
			
//			cerr<<rtc<<"????"<<cnt<<endl;
		}
		if(op==2)
		{
//			cerr<<"o!\n";
			cout<<ask(loc,rt[ver])<<endl;
//			cerr<<endl;
		}
		rt[i]=cnt;
	}
	return 0;
}