可持久化数组（可持久化线段树/平衡树）模板

题目

https://www.luogu.org/problemnew/show/P3919

代码

扔下代码赶紧跑。。。T_T
数组写法
评测结果：
https://www.luogu.org/recordnew/show/15185965

#include<bits/stdc++.h>
#define up(i,a,b) for (register int i=a;i<=b;++i)
#define down(i,a,b) for (register int i=a;i>=b;--i)
using namespace std;
const int maxn=2e7+1,maxm=1e6+1;
inline int read()
{
	int f=1,num=0;
	char ch=getchar();
	while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
	while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48), ch=getchar();
	return num*f;
}
struct Chairman
{
	int rt[maxm],val[maxn],lef[maxn],rig[maxn];
	int tail;
	int build(int l,int r)
	{
		int root=++tail;
		if (l==r)
		{
			val[root]=read();
			return root;
		}
		int mid=(l+r)>>1;
		lef[root]=build(l,mid);
		rig[root]=build(mid+1,r);
		return root;
	}
	int change(int now,int l,int r,int &x,int &y)
	{
		int root=++tail;
		if (l==r)
		{
			val[root]=y;
			return root;
		}
		lef[root]=lef[now],rig[root]=rig[now];
		int mid=(l+r)>>1;
		if (x<=mid) lef[root]=change(lef[now],l,mid,x,y);
		else rig[root]=change(rig[now],mid+1,r,x,y);
		return root;
	}
	void ask(int now,int l,int r,int &x)
	{
		if (l==r)
		{
			printf("%d\n",val[now]);
			return ;
		}
		int mid=(l+r)>>1;
		if (x<=mid) ask(lef[now],l,mid,x);
		else ask(rig[now],mid+1,r,x);
	}
}a;
int main()
{
	int n=read(),m=read();
	a.build(1,n);
	a.rt[0]=1;
	up(i,1,m)
	{
		int vers=read(),opt=read(),x=read();
		if (opt==1)
		{
			int y=read();
			a.rt[i]=a.change(a.rt[vers],1,n,x,y);
		}
		else
		{
			a.rt[i]=a.rt[vers];
			a.ask(a.rt[i],1,n,x);
		}
	}
	return 0;
}

结构体写法，这个跑得快。。。。。。
评测结果：
https://www.luogu.org/recordnew/show/15186173

#include<bits/stdc++.h>
#define up(i,a,b) for (register int i=a;i<=b;++i)
#define down(i,a,b) for (register int i=a;i>=b;--i)
using namespace std;
const int maxn=2e7+1;
inline int read()
{
	int f=1,num=0;
	char ch=getchar();
	while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
	while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48), ch=getchar();
	return num*f;
}
struct Chairman
{
    int l,r,val;
}tree[maxn];
int top,a[maxn],rt[maxn];
int build(int l,int r)
{
    int root=++top;
    if (l==r)
	{
        tree[root].val=a[l];
        return root;
    }
    int mid=(l+r)>>1;
    tree[root].l=build(l,mid);
    tree[root].r=build(mid+1,r);
    return root;
}

int change(int now,int l,int r,int &x,int &y)
{
    int root=++top;//更新就要新建节点
    tree[root]=tree[now];//全部信息都传到新节点
    if (l==r)
	{
        tree[root].val=y;
        return root;
    }
    int mid=(l+r)>>1;
    if (x<=mid)
        tree[root].l=change(tree[now].l,l,mid,x,y);  //访问左子树 
    else
        tree[root].r=change(tree[now].r,mid+1,r,x,y);  //访问右子树 
    return root;
}
int ask(int now,int l,int r,int x)
{
    if (l==r)
    {
    	return tree[now].val;
	}
	int mid=(l+r)>>1;
    if (x<=mid)
        return ask(tree[now].l,l,mid,x);//访问左子树
    else
        return ask(tree[now].r,mid+1,r,x);//访问右子树
}
int main()
{
    int n=read(),m=read();
    up(i,1,n)
		a[i]=read();
    build(1,n);//root[i]为i版本的根编号，刚开始编号为0
    rt[0]=1;
	up(i,1,m)
	{
        int vers=read(),opt=read(),x=read();
        if (opt==1)
		{
            int y=read();
            rt[i]=change(rt[vers],1,n,x,y);//保存版本
        }
        else
		{
            printf("%d\n",ask(rt[vers],1,n,x));//输出
            rt[i]=rt[vers];//新建版本
        }
    }
}