【Luogu P3919】可持久化数组

数组是一种单点修改，单点查询的基础数据结构。

如果要对数组改进，使之可持久化，那么显然我们需要利用其它的数据结构来改进它。

对于单点修改和单点查询两种操作，很容易发现可持久化线段树也是支持这种操作的。

所以，我们利用可持久化线段树来维护一个可持久化数组

#include<cstdio>

#define mid ((l+r)>>1)

using namespace std;

const int maxn=1e6+5;

int tot,tree[maxn*20],ls[maxn*20],a[maxn],rs[maxn*20],rt[maxn],n,m,v,flag,loc,val;

int build(int l,int r)

{

	int now=++tot;

	if (l==r)

	{

		tree[now]=a[l];

		return now;

	}

	ls[now]=build(l,mid);

	rs[now]=build(mid+1,r);

	return now;

}

int update(int root,int l,int r,int pnt,int val)

{

	int now=++tot;

	ls[now]=ls[root];

	rs[now]=rs[root];

	if (l==r&&l==pnt)

	{

		tree[now]=val;

		return now;

	}

	else

	{

		if (l==r) return now;

		if (pnt<=mid) ls[now]=update(ls[now],l,mid,pnt,val);

		if (pnt>mid) rs[now]=update(rs[now],mid+1,r,pnt,val);

		return now;

	}

}

int query(int root,int l,int r,int pnt)

{

	if (l==r&&l==pnt)

		return tree[root];

	int ret;

	if (pnt<=mid) ret=query(ls[root],l,mid,pnt);

	if (pnt>mid) ret=query(rs[root],mid+1,r,pnt);

	return ret;

}

int main()

{

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	rt[0]=build(1,n);

	for (int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&v,&flag,&loc);

		if (flag==1)

		{

			scanf("%d",&val);

			rt[i]=update(rt[v],1,n,loc,val);

		}

		else

		{

			rt[i]=rt[v];

			printf("%d\n",query(rt[v],1,n,loc));

		}

	}

	return 0;

}

巴特西

【Luogu P3919】可持久化数组

最新文章

热门文章