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

Broadway · 2017-12-11 21:59:25 · 题解

题目只要求单点修改，单点查询历史版本……所以可持久化线段树还挺好写虽然WA了n次…………注意之前我因为懒没有把新建节点传进过程里面……结果栈空间溢出交上去全MLE……这里提醒一句

没人会犯我这种蒟蒻才犯的错误了吧

因为每次修改都会增加logn个节点，最大修改次数是1000000次

n最大也是1000000，logn大概是20，所以开20倍n多一点的数组比较稳

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
const int maxn=1000005;
struct Node
{
    int sum,lch,rch;
}tree[maxn*20];
int rt[maxn],tot,curver,n,m;
inline void init() { tot=0; curver=0; }
inline void up(int p) { tree[p].sum=tree[tree[p].lch].sum+tree[tree[p].rch].sum; }
inline int read()
{
    int f=1,x=0; char ch;
    do { ch=getchar(); if(ch=='-') f=-1; } while(ch<'0'||ch>'9');
    do { x=x*10+ch-'0'; ch=getchar(); } while(ch>='0'&&ch<='9');
    return f*x;
}
int build(int l,int r,int cp)
{
    tree[cp].sum=0; tree[cp].lch=-1; tree[cp].rch=-1;
    if (l==r) { tree[cp].sum=read(); return cp; }
    int m=l+r>>1;
    tree[cp].lch=build(l,m,tot++); tree[cp].rch=build(m+1,r,tot++);
    up(cp);
    return cp;
}
int update(int p,int l,int r,int x,int k,int cp)
{
    tree[cp].sum=0; tree[cp].lch=tree[p].lch; tree[cp].rch=tree[p].rch;
    if (l==r) { tree[cp].sum=k; return cp; }
    int m=l+r>>1;
    if (x<=m) tree[cp].lch=update(tree[p].lch,l,m,x,k,tot++); else tree[cp].rch=update(tree[p].rch,m+1,r,x,k,tot++);
    up(cp);
    return cp;
}
int query(int p,int l,int r,int x)
{
    if (l==r) return tree[p].sum;
    int m=l+r>>1;
    if (x<=m) return query(tree[p].lch,l,m,x); else return query(tree[p].rch,m+1,r,x);
}
int main()
{
    int v,c,s,k;
    n=read(); m=read();
    init();
    rt[curver]=build(1,n,tot++);
    for (int i=1;i<=m;i++)
    {
        v=read(); c=read(); s=read();
        if (c==1)
        {
            k=read();
            rt[++curver]=update(rt[v],1,n,s,k,tot++);
        }
        else if (c==2)
        {
            rt[++curver]=rt[v];
            printf("%d\n",query(rt[v],1,n,s));
        }
    }
    return 0;
}
```cpp