HDU 4388 To the moon

To the moon

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Background

To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.

You‘ve been given $N$ integers $A_1, A_2, dots, A_n$. On these integers, you need to implement the following operations:
1. C $l$ $r$ $d$: Adding a constant $d$ for every ${A_i mid l le i le r }$, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.
2. Q $l$ $r$: Querying the current sum of ${A_i mid l le i le r}$.
3. H l r t: Querying a history sum of {A_i | l <= i <= r} in time t.
4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
.. N, M ≤ 10⁵, |A_[i]| ≤ 10⁹, 1 ≤ l ≤ r ≤ N, |d| ≤ 10⁴ .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state.

Input

n m
A₁ A₂ ... A_n
... (here following the m operations. )

Output

... (for each query, simply print the result. )

Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

2 4

0 0

C 1 1 1

C 2 2 -1

Q 1 2

H 1 2 1

Sample Output

4

55

9

15

0

1

Author

HIT

Source

2012 Multi-University Training Contest 5

Solution

裸的可持久化线段树，但卡空间，只给 64 M。这是我写的第 3 道可持久化线段树的题目。

这篇随笔主要讨论：可持久化线段树在维护区间更新（相对于单点更新而言）操作，需要打懒标记（lazy-tag，以下简称“标记”或“tag”）时如何节省空间（内存）。

另外这个题目还涉及到一个“时间倒流”的操作——回到线段树的某个之前版本并删除在此之后的所有版本，我们也简单讨论下在这个操作后如何回收后续版本占用的空间。

可持久化数据结构用于维护某个数据结构的不同历史版本，在逻辑上我们应当认为这些不同的version属于同一个object。一般来说，一个数据结构由若干元素构成，可持久化数据结构的思想是：相邻两个版本共用相同元素，在后一版本中只新建被更改了的元素。线段树（属于二叉树）的元素就是节点，节点维护着某个区间的信息。

当我们修改一个节点时当然要新建一个节点作为该节点的当前版本；如果该节点上有标记，非可持久化线段树的写法是：先将该标记push-down到两个子节点上，然后把当前节点的标记消除，最后再从两个子节点push-up来更新该节点。如果可持久化线段树也按这种方式处理标记，那么每次push-down就需要新建两个子节点，这两个子节点是和修改之前的父节点同一版本的，而不是当前版本的（“当前版本”是指修改之后的父节点的版本）。这样在query和update的过程中，push-down会新建大量节点，而且这么做还有一个弊端——它导致属于同一版本的新建节点在数组中不连续，这一点后面还会谈到。

对于标记还有另为一种处理方法——Never push down。

在 query 或 update 的过程中不 push-down 任何节点的 tag，查询时，如果当前节点有标记，就把该标记对要查询的区间 $[l, r]$ 和该节点表示的区间 $[L, R]$ 的交集 $[max(l, L), min(r, R)]$ 的贡献更新到答案中去。

这么做的效果就是：

只有被修改了的节点才会被新建，而这正是我们所期望的。（注意：从逻辑上讲，上个方法中 push-down 新建的那两个子节点在之前的某个本中就存在了，只是没有建出来。）
属于同一版本的新建节点在数组中是连续的，而且显然相邻版本的新建节点也是相邻的。

这样对于回到 $t$ 时刻的“时间倒流”操作，只要把数组的 $mathrm{tail}$ 直接置成 $mathrm{tail}_t$ 就好了。（$t$ 时刻内新建的节点在 $[mathrm{tail}_{t-1}, mathrm{tail}_t)$ 区间内）

Implementation

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5, M=2.5e6+5;
typedef long long LL;
int ls[M], rs[M], tail, now, root[N];
LL add[M], sum[M];

void push_up(int id){
    sum[id]=sum[ls[id]]+sum[rs[id]];
}

int get_cur(int id, int now){
    return tail++;
}

LL query(int id, int L, int R, int l, int r){
    if(l>R || L>r) return 0;
    if(l<=L && R<=r) return sum[id];
    int mid=L+R>>1;
    return add[id]*(min(R, r)-max(L, l)+1)+query(ls[id], L, mid, l, r)+query(rs[id], mid+1, R, l, r);
}

int Add(int id, int L, int R, int l, int r, int v){
    if(l>R || L>r)  return id;
    int cur=get_cur(id, now);

    add[cur]=add[id], sum[cur]=sum[id]+(min(R, r)-max(L, l)+1)*v;   //copy tag only

    if(l<=L && R<=r){
        add[cur]+=v;
        ls[cur]=ls[id], rs[cur]=rs[id];
    }

    else{
        int mid=L+R>>1;
        ls[cur]=Add(ls[id], L, mid, l, r, v);
        rs[cur]=Add(rs[id], mid+1, R, l, r, v);
    }
    return cur;
}

void init(int id, int L, int R){
    add[id]=0;
    if(L==R){
        scanf("%lld", sum+id);
        return;
    }
    int mid=L+R>>1;
    init(ls[id]=tail++, L, mid);
    init(rs[id]=tail++, mid+1, R);
    push_up(id);
}

int main(){
    // cout<<M<<endl;
    for(int n, m; cin>>n>>m; ){
        now=0, tail=0, init(root[now]=tail++, 1, n);
        char op[2];
        int l, r, d, t;

        for(; m--; ){
            scanf("%s", op);
            if(*op=='C'){
                scanf("%d%d%d", &l, &r, &d);
                ++now, root[now]=Add(root[now-1], 1, n, l, r, d);    //error-prone
            }
            else if(*op=='Q'){
                scanf("%d%d", &l, &r);
                printf("%lld
", query(root[now], 1, n, l, r));
            }
            else if(*op=='H'){
                scanf("%d%d%d", &l, &r, &t);
                printf("%lld
", query(root[t], 1, n, l, r));    //error-prone
            }
            // you can never access a forward edition anymore.
            else scanf("%d", &t), now=t;
        }
    }
}