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

As you see

// luogu-judger-enable-o2

#include<cstdio>

#include<cstring>

#include<algorithm>

inline int read () {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9'){if(c=='-')f=-1; c=getchar();}

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x*f;

}

const int maxn = 1000007;

int n,m,a[maxn],tot = 0,root[maxn];

struct Chairman_Tree {

    int ch[2],num ;

} ;

Chairman_Tree t[maxn << 4];

#define lc t[x].ch[0]

#define rc t[x].ch[1]

void build(int & x,int l,int r) {

    x = ++ tot;

    if(l == r) {

        t[x].num = a[l];return ;

    }

    int mid = l + r >> 1;

    build(lc,l,mid); build(rc,mid+1,r);return ;

}

int query(int x,int l,int r,int pos) {

    if(l == r) return t[x].num;

    int mid = l + r >>1;

    if(pos <= mid) return query(lc,l,mid,pos);

    else return query(rc,mid+1,r,pos);

}

void modify(int pre,int &x,int l,int r,int pos,int w) {

    t[x = ++tot] = t[pre];

    if(l == r) {

        t[x].num = w;return ;

    }

    int mid = l + r >> 1;

    if(pos <= mid) modify(t[pre].ch[0],lc,l,mid,pos,w);

    else modify(t[pre].ch[1],rc,mid + 1,r,pos,w);

}

int main () {

    n = read(),m = read();

    for(int i = 1;i <= n;++ i) a[i] = read();

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

    for(int T,op,a,b,i = 1;i <= m;++ i) {

        T = read(),op = read();

        if(op == 1) {

            a = read(),b = read();

            modify(root[T],root[i],1,n,a,b);

        }

        else {

            a = read(),root[i] = root[T];

            printf("%d\n",query(root[T],1,n,a));

        }

    }

    return 0;

}

巴特西

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

最新文章

热门文章