To the moon(可持久化线段树区间更新)

描述

传送门:HDU4348

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],…, 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 | l ≤ i ≤ 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 | l ≤ i ≤ 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^5$, $|A[i]| ≤ 10^9$, $1 ≤ l ≤ r ≤ N$, $|d| ≤ 10^4$ … 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.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
4
55
9
15

0
1

思路

  • 可以想到用可持久化线段树做区间更新。这样每次更新的时候,没有更新的结点就可以引用历史版本。
  • 但是在查询的时候,懒惰标记下传会更新子树。在可持久化线段树中,我们的子树是历史版本的引用,固然不能更新;而如果新建新的结点,就会造成大量的空间开销。
  • 因此在可持久化线段树中,我们要把懒惰标记永久化。
  • 直接把当前区间的懒惰标记用一个参数传下去,然后找到要求和的区间时,直接把从上到下的懒惰标记累加和乘以区间长度再加上这段区间原本的和就可以了。
  • 由于懒惰标记没有下传,所以在pushup的时候,也需要考虑标记造成的影响。
  • 在版本回退的时候,可以把空间回收。
  • 具体实现看代码,感觉有时候指针版本还是比较好看好写的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
using namespace std;

typedef long long ll;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

struct Node
{
Node *lson, *rson;
int addv;
ll sumv;
};

void pushup(Node* o, int m) { o->sumv = o->lson->sumv + o->rson->sumv + 1LL * o->addv * m; }
const int N = 100002;
Node mem[N * 30];
int tot = 0;

void build(int l, int r, Node*& o)
{
o = &mem[++tot];
o->addv = 0;
if (l == r)
{
scanf("%lld", &o->sumv);
return;
}
int m = l + r >> 1;
build(l, m, o->lson);
build(m + 1, r, o->rson);
pushup(o, r - l + 1);
}

void update(int L, int R, int v, int l, int r, Node*& o, Node* p)
{
o = &mem[++tot];
*o = *p;
if (L <= l && r <= R)
{
o->addv += v;
o->sumv += 1LL * v * (r - l + 1);
return;
}
int m = l + r >> 1;
if (L <= m) update(L, R, v, l, m, o->lson, p->lson);
if (m < R) update(L, R, v, m + 1, r, o->rson, p->rson);
pushup(o, r - l + 1);
}

ll query(int L, int R, int l, int r, int addv, Node* o)
{
if (L <= l && r <= R) return o->sumv + 1LL * addv * (r - l + 1);
addv += o->addv; // pushdown
int m = l + r >> 1;
ll sum = 0;
if (L <= m) sum += query(L, R, l, m, addv, o->lson);
if (m < R) sum += query(L, R, m + 1, r, addv, o->rson);
return sum;
}

Node* root[N];

void go()
{
int n, m;
bool flag = 0;
while (~scanf("%d%d", &n, &m))
{
if (flag) puts("");
flag = 1;
char op[5];
int l, r, d, t;
int T = 0;
build(1, n, root[0]);
while (m--)
{
scanf("%s", op);
if (op[0] == 'C')
{
scanf("%d%d%d", &l, &r, &d);
++T;
update(l, r, d, 1, n, root[T], root[T - 1]);
}
else if (op[0] == 'Q')
{
scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r, 1, n, 0, root[T]));
}
else if (op[0] == 'H')
{
scanf("%d%d%d", &l, &r, &t);
printf("%lld\n", query(l, r, 1, n, 0, root[t]));
}
else
{
scanf("%d", &T);
tot = root[T + 1] - root[0];
}
}
tot = 0;
}
}
捐助作者
0%