代码

//可持久化线段树

#include <cstdio>

using namespace std;

struct node

{

    node *Lnode,*Rnode;

    int val;

    void clone(node* N)

    {

        Lnode=N->Lnode;

        Rnode=N->Rnode;

        val=N->val;

        return;

    }

}tree[20000005],*root[1000005],*tail=tree;

int a[1000005];

node* build(int L,int R)

{

    node *N=(++tail);

    if(L==R)

    {

        N->val=a[L];

        return N;

    }

    int M=(L+R)>>1;

    N->Lnode=build(L,M);

    N->Rnode=build(M+1,R);

    return N;

}

node* modify(node* N,int L,int R,int pos,int val)

{

    node *O=(++tail);

    O->clone(N);

    if(L==R)

    {

        O->val=val;

        return O;

    }

    int M=(L+R)>>1;

    if(pos<=M) O->Lnode=modify(N->Lnode,L,M,pos,val);

    else O->Rnode=modify(N->Rnode,M+1,R,pos,val);

    return O;

}

int query(node* N,int L,int R,int pos)

{

    if(L==R) return N->val;

    int M=(L+R)>>1;

    if(pos<=M) return query(N->Lnode,L,M,pos);

    return query(N->Rnode,M+1,R,pos);

}

int main()

{

    int n,m;

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

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

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

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

    {

        int v,opt,loc;

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

        if(opt==1)

        {

            int val;

            scanf("%d",&val);

            root[i]=modify(root[v],1,n,loc,val);

        }

        else

        {

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

            root[i]=root[v];

        }

    }

    return 0;

}