P3919 【模板】可持久化线段树 1（可持久化数组）

#include <bits/stdc++.h>
using namespace std;
const int mn=1e6+7;
struct ccf{
	long long l,r,val;
}tree[mn*20];
long long w[mn],root[mn],len=0;
void build(long long &k,long long l,long long r)
{
	k=++len;
	if(l==r)
	{
		tree[k].val=w[l];
		return ;
	}
	long long m=(l+r)>>1;
	build(tree[k].l,l,m);
	build(tree[k].r,m+1,r);
}
void up(long long re,long long &k,long long l,long long r,long long x,long long v)
{
	k=++len;
	tree[k]=tree[re];
	if(l==r)
	{
		tree[k].val=v;
		return ;
	}
	long long m=(l+r)>>1;
	if(x<=m)  up(tree[re].l,tree[k].l,l,m,x,v);
	else  up(tree[re].r,tree[k].r,m+1,r,x,v);
}
long long ask(long long k,long long l,long long r,long long x)
{
	if(l==r)  return tree[k].val;
	long long m=(l+r)>>1;
	if(x<=m)  return ask(tree[k].l,l,m,x);
	return ask(tree[k].r,m+1,r,x);
}
int main()
{
	long long n,m;
	cin>>n>>m;
	for(long long i=1;i<=n;++i)
	  scanf("%lld",&w[i]);
	build(root[0],1,n);
	for(long long i=1;i<=m;++i)
	{
		long long k,op;
		scanf("%lld%lld",&k,&op);
		if(op==1)
		{
			long long x,v;
			scanf("%lld%lld",&x,&v);
			up(root[k],root[i],1,n,x,v);
		}
		else
		{
			long long x;
			scanf("%lld",&x);
			printf("%lld
",ask(root[k],1,n,x));
			root[i]=root[k];
		}
	}
}