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

Treaker · 2019-09-16 17:01:52 · 题解

指针题解来一发！！！

指针题解寥寥无几，表示不服！！！

我们就根据题意可持久化就行了！！！

之前这里我犯了一个致命错误，如下：

void insert(node *&p,node *A,int x,int val)
{
    p = new (tail ++)node(); p = A;
    if(p -> l == p -> r) return (void)(p -> val = val);
    if(x <= mid) insert(p -> ls,A -> ls,x,val);
    else insert(p -> rs,A -> rs,x,val);
}

这里不能直接把A赋给p，因为我们的p带着取地址符，修改p时也会把A修改了；

修改后如下：

void insert(node *&p,node *A,int x,int val)
{
    p = new (tail ++)node(A -> l,A -> r); p -> ls = A -> ls;p -> rs = A -> rs;p -> val = A -> val;
    if(p -> l == p -> r) return (void)(p -> val = val);
    if(x <= mid) insert(p -> ls,A -> ls,x,val);
    else insert(p -> rs,A -> rs,x,val);
}

也可以这样写

void insert(node *&p,node *A,int x,int val)
{
    p = new (tail ++)node(); *p = *A;
    if(p -> l == p -> r) return (void)(p -> val = val);
    if(x <= mid) insert(p -> ls,A -> ls,x,val);
    else insert(p -> rs,A -> rs,x,val);
}

这样比较简洁。

全部代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
inline int read()
{
    int x = 0 , f = 1;  char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')  f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int n , m , a[N];
struct Segment_tree
{
    #define mid ((p -> l + p -> r) >> 1)
    struct node
    {
        node *ls , *rs;
        int l , r , val;
        node (int l = 0,int r = 0) : l(l) , r(r) {val = 0;ls = rs = NULL;}
    }*root[N << 1] , pool[N * 13] , *tail;
    void build(node *&p,int l,int r)
    {
        p = new (tail ++)node(l,r);
        if(l == r) return (void)(p -> val = a[l]);
        build(p -> ls,l,mid);
        build(p -> rs,mid+1,r);
    }
    void insert(node *&p,node *A,int x,int val)
    {
        p = new (tail ++)node(); *p = *A;
        if(p -> l == p -> r) return (void)(p -> val = val);
        if(x <= mid) insert(p -> ls,A -> ls,x,val);
        else insert(p -> rs,A -> rs,x,val);
    }
    int query(node *p,int x)
    {
        if(p -> l == p -> r) return p -> val;
        if(x <= mid) return query(p -> ls,x);
        return query(p -> rs,x);
    }
    inline void LOL()
    {
        n = read(); m = read();
        for(int i = 1;i <= n;i ++)  a[i] = read();
        build(root[0],1,n);
        for(int i = 1 , v , opt , loc , val;i <= m;i ++)
        {
            v = read(); opt = read(); loc = read();
            if(opt & 1) val = read() , insert(root[i],root[v],loc,val);
            else printf("%d\n",query(root[v],loc)) , root[i] = root[v];
        }
    }
    Segment_tree() {tail = pool;}
}CF;
int main()
{   
    CF.LOL();
    return 0;
}