思路：对于每个历史版本保存一个根节点

样例都没过

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read(),m=read();
ll now,idx=1,a[N],root[N];
struct node{ll l,r,ls,rs,val;}t[N<<2];
inline void build(ll p,ll l,ll r)
{
	t[p].l=l,t[p].r=r;
	if(l==r)
	{
		t[p].val=a[l];
		return;
	}
	rll mid=l+r>>1;
	t[p].ls=++idx,build(t[p].ls,l,mid);
	t[p].rs=++idx,build(t[p].rs,mid+1,r);
}
inline void change(ll p,ll x,ll k)
{
	if(t[p].l==t[p].r)
	{
		t[p].val=k;
		return;
	}
	rll mid=t[p].l+t[p].r>>1;
	if(x<=mid)
	{
		change(t[p].ls,x,k);
		t[++idx].l=t[t[p].ls].l,t[idx].ls=t[p].ls;
		if(p==now) root[now]=idx;
	}
	else
	{
		change(t[p].rs,x,k);
		t[++idx].r=t[t[p].rs].r,t[idx].rs=t[p].rs;
		if(p==now) root[now]=idx;
	}
}
inline ll query(ll p,ll x)
{
	if(t[p].l==t[p].r) return t[p].val;
	rll mid=t[p].l+t[p].r>>1;
	if(x<=mid) return query(t[p].ls,x);
	else return query(t[p].rs,x);
}
int main()
{
    for(rll i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    root[0]=1;
    for(rll i=1,v,x,op,val;i<=m;i++)
    {
    	v=read(),op=read(),x=read();
    	if(op==1)
		{
			val=read(),now=i;
			change(root[v],x,val);
		}
    	else
		{
			now=-1,root[i]=root[i-1];
			write(query(root[v],x)),putchar('\n');
		}
	}
    return 0;
}