可持久化数组

Cobalt · 2018-10-18 09:10:06 · 个人记录

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

#include<cstdio>
#define N 2000010
#define LOG 25
using namespace std;
int T[N],L[N*LOG],R[N*LOG],val[N*LOG];
int n,m,q,tot;
int update(int pre,int l,int r,int p,int k){
    int x=++tot;
    L[x]=L[pre];
    R[x]=R[pre];
    if(l==r)
        val[x]=k;
    if(l<r){
        int mid=(l+r)>>1;
        if(p<=mid)
            L[x]=update(L[x],l,mid,p,k);
        else
            R[x]=update(R[x],mid+1,r,p,k);
    }
    return x;
}
int query(int x,int l,int r,int p){
    if(l==r)
        return val[x];
    int mid=(l+r)>>1;
    if(p<=mid)
        return query(L[x],l,mid,p);
    else
        return query(R[x],mid+1,r,p);
}
int main(){
    scanf("%d%d",&n,&m);
    int t;
    for(int i=1;i<=n;i++){
        scanf("%d",&t);
        T[i]=update(T[i-1],1,n,i,t);
    }
    int opt,x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&opt,&y);
        if(opt==1){
            scanf("%d",&z);
            T[n+i]=update(T[n+x],1,n,y,z);
        }
        else{
            T[n+i]=T[n+x];
            printf("%d\n",query(T[n+x],1,n,y));
        }
    }
    return 0;
}