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

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid (l+r)/2
struct node{int ls,rs,c;}tr[N*40];int trlen,rt[N],a[N];

void change(int pre,int &now,int l,int r,int x,int c)
{
	now=++trlen;tr[now]=tr[pre];
	if(l==r){tr[now].c=c;return ;}
	if(x<=mid) change(lc(pre),lc(now),l,mid,x,c);
	else       change(rc(pre),rc(now),mid+1,r,x,c);
}
int query(int now,int l,int r,int x)
{
	if(l==r) return tr[now].c;
	if(x<=mid) return query(lc(now),l,mid,x);
	else       return query(rc(now),mid+1,r,x);
}	 
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	trlen=0;rt[0]=0;
	for(int i=1;i<=n;i++)change(rt[0],rt[0],1,n,i,a[i]);
	
	for(int i=1;i<=m;i++)
	{
		int t,op,x,c;scanf("%d%d",&t,&op);
		if(op==1)
		{
			scanf("%d%d",&x,&c);
			change(rt[t],rt[i],1,n,x,c);
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",query(rt[t],1,n,x));rt[i]=rt[t];
		}	
	}
	return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid (l+r)/2
struct node{int ls,rs,c;}tr[N*40];int trlen,rt[N],a[N];

void change(int pre,int &now,int l,int r,int x,int c)
{
	now=++trlen;tr[now]=tr[pre];
	if(l==r){tr[now].c=c;return ;}
	if(x<=mid) change(lc(pre),lc(now),l,mid,x,c);
	else       change(rc(pre),rc(now),mid+1,r,x,c);
}
int query(int now,int l,int r,int x)
{
	if(l==r) return tr[now].c;
	if(x<=mid) return query(lc(now),l,mid,x);
	else       return query(rc(now),mid+1,r,x);
}	 
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	trlen=0;rt[0]=0;
	for(int i=1;i<=n;i++)change(rt[0],rt[0],1,n,i,a[i]);
	
	for(int i=1;i<=m;i++)
	{
		int t,op,x,c;scanf("%d%d",&t,&op);
		if(op==1)
		{
			scanf("%d%d",&x,&c);
			change(rt[t],rt[i],1,n,x,c);
		}
		else
		{
			scanf("%d",&x);
			printf("%d\n",query(rt[t],1,n,x));rt[i]=rt[t];
		}	
	}
	return 0;
}