[洛谷P3919]【模板】可持久化数组

题目大意：有两个操作，1：在第x次操作后的版本上修改一个值，2：查询在第x次操作后的版本上的一个节点的值

即：

你需要维护这样的一个长度为N的数组，支持如下几种操作

　　1.在某个历史版本上修改某一个位置上的值

　　2.访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

题解：主席树，即针对每个询问建一棵线段树，但这样会MLE，不过我们可以发现由于相邻线段树的公共部分很多，可以充分利用，达到优化目的，同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。每次修改最多增加O(log n)的空间，所以总的空间复杂度是O(n log n)

C++ Code：

#include<cstdio>

using namespace std;

const int maxn=20000100;

int root[1001000],lc[maxn],rc[maxn],val[maxn],cnt;

int n,m;

void build(int &rt,int l,int r){

	rt=++cnt;

	if (l==r){

		scanf("%d",&val[rt]);

		return;

	}

	int mid=l+r>>1;

	build(lc[rt],l,mid);

	build(rc[rt],mid+1,r);

}

void add(int &rt,int ver,int l,int r,int x,int y){

	rt=++cnt;

	lc[cnt]=lc[ver];rc[cnt]=rc[ver];

	if (l==r){

		val[rt]=y;

		return;

	}

	int mid=l+r>>1;

	if (x<=mid)add(lc[rt],lc[ver],l,mid,x,y);

		else add(rc[rt],rc[ver],mid+1,r,x,y);

}

void ask(int rt,int l,int r,int x){

	if (l==r){

		printf("%d\n",val[rt]);

		return;

	}

	int mid=l+r>>1;

	if (x<=mid)ask(lc[rt],l,mid,x);

		else ask(rc[rt],mid+1,r,x);

}

int main(){

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

	build(root[0],1,n);

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

		int num,ope,x,y;

		scanf("%d%d",&num,&ope);

		if (ope==1){

			scanf("%d%d",&x,&y);

			add(root[i],root[num],1,n,x,y);

		}else{

			scanf("%d",&x);

			ask(root[num],1,n,x);

			root[i]=root[num];

		}

	}

	return 0;

}

巴特西

[洛谷P3919]【模板】可持久化数组

最新文章

热门文章