【模板】可持久化数组

题解：

主席树随便搞搞就行了

取消同步发现cin在开O2后比scanf要快啊。。。

代码：

#include <bits/stdc++.h>
using namespace std;
#define N 1500010
#define rg register
#define IL inline 
int a[N],root[N],cnt,n,m;
int ls[N*12],rs[N*12],p[N*12];
#define mid (h+t)/2
IL void build(int &now,int h,int t)
{
    if (now==0) now=++cnt;
    if (h==t)
    {
      p[now]=a[h]; 
      return;
    }
    build(ls[now],h,mid);
    build(rs[now],mid+1,t);
}
IL void change(int la,int &now,int h,int t,int pos,int goal)
{
    now=++cnt;
    ls[now]=ls[la]; rs[now]=rs[la];
    if (h==t)
    {
        p[now]=goal; return;
    }
    if (pos<=mid)
    {
        change(ls[la],ls[now],h,mid,pos,goal);
    } else
    {
        change(rs[la],rs[now],mid+1,t,pos,goal);
    }
}
int query(int x,int h,int t,int pos)
{
    if (h==t) return(p[x]);
    if (pos<=mid) return(query(ls[x],h,mid,pos));
    else return(query(rs[x],mid+1,t,pos));
}
int main()
{
    scanf("%d%d",&n,&m);
    for (rg int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    build(root[0],1,n);
    for (rg int i=1;i<=m;i++)
    {
        int v,x,y,z;
        scanf("%d%d",&v,&x);
        if (x==2)
        {
            scanf("%d",&y);
            root[i]=root[v];
            cout<<query(root[v],1,n,y)<<endl;
        } else
        {
            scanf("%d%d",&y,&z);
            change(root[v],root[i],1,n,y,z);
        }
    }
    return 0;
}