[LUOGU]3919 【模板】可持久化数组

用可持久化线段树维护可持久化数组。可持久化线段树见之前发的主席树模板

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int n,m;

const int N=22000001;

int rt[N],l[N],r[N],t[N],cnt;

int build(int L,int R) {

    int root=++cnt;

    if(L==R) {

        scanf("%d",&t[root]);

        return root;

    }

    l[root]=build(L,L+R>>1);

    r[root]=build(1+(L+R>>1),R);

    return root;

}

int update(int pre,int L,int R,int c,int x) {

    int root=++cnt;

    if(L==R) {

        t[root]=c;

        return root;

    }

    l[root]=l[pre];

    r[root]=r[pre];

    int mid=L+R>>1;

    if(x<=mid) l[root]=update(l[pre],L,mid,c,x);

    else r[root]=update(r[pre],mid+1,R,c,x);

    return root;

}

int query(int pre,int L,int R,int c) {

    if(L==R) {

        return t[pre];

    }

    int mid=L+R>>1;

    if(c<=mid) return query(l[pre],L,mid,c);

    else return query(r[pre],mid+1,R,c);

}

int main() {

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

    build(1,n);

    rt[0]=1;

    int opt,a,b,c;

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

        scanf("%d%d",&a,&opt);

        if(opt==1) {

            scanf("%d%d",&b,&c);

            rt[i]=update(rt[a],1,n,c,b);

        } else {

            scanf("%d",&b);

            rt[i]=rt[a];

            printf("%d\n",query(rt[a],1,n,b));

        }

    }

}

巴特西

[LUOGU]3919 【模板】可持久化数组

最新文章

热门文章