rt，可持久化线段树

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,m,top,op,x,y,z,a[N],r[N];
struct{int ls,rs,x;} t[N];
inline int clone(int p)
{
	t[++top]=t[p];
	return top;
}
int bulid(int l,int r)
{
    int p=++top;
    if(l==r)
    {
        t[p].x=a[l];
        return p;//
    }
    int m=l+r>>1;
    t[p].ls=bulid(l,m);
    t[p].rs=bulid(m+1,r);
    return p;
}
int update(int p,int l,int r,int x,int y)
{
	int P=clone(p);
	if(l==r)	t[P].x=x;
	else
	{
		int m=l+r>>1;
		if(x<=m)	t[P].ls=update(t[P].ls,l,m,x,y);
		else	t[P].rs=update(t[P].rs,m+1,r,x,y);
	}
	return P;
}
int query(int p,int l,int r,int x)
{
	if(l==r)	return t[p].x;
	int m=l+r>>1;
	if(x<=m)	return query(t[p].ls,l,m,x);
	return query(t[p].rs,m+1,r,x);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>a[i];
    r[0]=bulid(1,n);
    for(int i=1;i<=m;i++)
    {
    	cin>>x>>op;
    	if(op==1)
    	{
    		cin>>y>>z;
    		r[i]=update(r[x],1,n,y,z);
		}
    	else
		{
    		cin>>y;
    		cout<<query(r[x],1,n,y)<<'\n';
    		r[i]=r[x];
		}
	}
    return 0;
}