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

代码

#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;
}

原文：https://www.cnblogs.com/C-C-C-P/p/10393681.html