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

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+, M=2.5e6+;

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 ;

    if(l<=L && R<=r) return sum[id];

    int mid=L+R>>;

    return add[id]*(min(R, r)-max(L, l)+)+query(ls[id], L, mid, l, r)+query(rs[id], mid+, 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)+)*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>>;

        ls[cur]=Add(ls[id], L, mid, l, r, v);

        rs[cur]=Add(rs[id], mid+, R, l, r, v);

    }

    return cur;

}

void init(int id, int L, int R){

    add[id]=;

    if(L==R){

        scanf("%lld", sum+id);

        return;

    }

    int mid=L+R>>;

    init(ls[id]=tail++, L, mid);

    init(rs[id]=tail++, mid+, R);

    push_up(id);

}

int main(){

    // cout<<M<<endl;

    for(int n, m; cin>>n>>m; ){

        now=, tail=, init(root[now]=tail++, , n);

        char op[];

        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-], , n, l, r, d);    //error-prone

            }

            else if(*op=='Q'){

                scanf("%d%d", &l, &r);

                printf("%lld\n", query(root[now], , n, l, r));

            }

            else if(*op=='H'){

                scanf("%d%d%d", &l, &r, &t);

                printf("%lld\n", query(root[t], , n, l, r));    //error-prone

            }

            // you can never access a forward edition anymore.

            else scanf("%d", &t), now=t;

        }

    }

}

巴特西

HDU 4388 To the moon