洛谷P2357-守墓人

很简单的线段树区间修改/查询裸题

题意概括

在一个荒凉的墓地上,有一个令人尊敬的守墓人, 他看守的墓地从来没有被盗过, 所以人们很放心的把自己的先人的墓安顿在他那

守墓人能看好这片墓地是必然而不是偶然……

因为……守墓人懂风水 0.0

他把墓地分为主要墓碑和次要墓碑, 主要墓碑只能有 1 个, 守墓人把他记为 1 号, 而次要墓碑有 n−1 个,守墓人将之编号为 2,3…n,所以构成了一个有 n 个墓碑的墓地。

而每个墓碑有一个初始的风水值,这些风水值决定了墓地的风水的好坏,所以守墓人需要经常来查询这些墓碑。

善于运用风水的守墓人,通过一次次逆天改命,使得自己拥有了无限寿命,没人知道他活了多久。这天,你幸运的拜访到了他,他要求你和他共同见证接下来几年他的战果,但不过他每次统计风水值之和都需要你来帮他计算,算错了他会要你命 QAQ

风水也不是不可变,除非遭遇特殊情况,已知在接下来的 2147483647 年里,会有 n 次灾难,守墓人会有几个操作:

  1. 将 [l,r] 这个区间所有的墓碑的风水值增加 kk

  2. 将主墓碑的风水值增加 kk

  3. 将主墓碑的风水值减少 kk

  4. 统计 [l,r] 这个区间所有的墓碑的风水值之和

  5. 求主墓碑的风水值

上面也说了,很多人会把先人的墓安居在这里,而且守墓人活了很多世纪→_→,墓碑的数量会多的你不敢相信= =

守墓人和善的邀请你帮他完成这些操作,要不然哪天你的旅馆爆炸了,天上下刀子…..

为了活命,还是帮他吧

题目分析

很简单的线段树裸题,题目涉及区间修改/单点修改,于是我们直接套用区间修改与查询的模板,时间复杂度为$O(NlogN)$。

代码

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
#include <bits/stdc++.h>
#define int long long
#define maxn 400005
using namespace std;

inline int read() {
char c = getchar();
int f = 1, _ = 0;
while (c > '9' || c < '0')
f = (c == '-') ? -1 : 1, c = getchar();
while (c <= '9' && c >= '0')
_ = (_ << 3) + (_ << 1) + (c ^ 48), c = getchar();
return _ * f;
}
int a[maxn], sumv[maxn << 1], lazy[maxn << 1];

inline void pushup(int id) {
sumv[id] = sumv[id << 1] + sumv[id << 1 | 1];
}

inline void pushdown(int id, int m) {
if (lazy[id]) {
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
sumv[id << 1] += lazy[id] * (m - (m >> 1));
sumv[id << 1 | 1] += lazy[id] * (m >> 1);
lazy[id] = 0;
}
}

inline void build(int id, int l, int r) {
if (l == r) {
sumv[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
pushup(id);
}

inline void update(int id, int l, int r, int x, int y, int v) {
if (x <= l && r <= y) {
sumv[id] += v * (r - l + 1);
lazy[id] += v;
return;
}
//cout << id << "<--" << l << " " << r << endl;
pushdown(id, r - l + 1);
int mid = (l + r) >> 1;
if (x <= mid)
update(id << 1, l, mid, x, y, v);
if (y > mid)
update(id << 1 | 1, mid + 1, r, x, y, v);
pushup(id);
}

inline int query(int id, int l, int r, int x, int y) {
if (x <= l && r <= y)
return sumv[id];
pushdown(id, r - l + 1);
int mid = (l + r) >> 1;
int ans = 0;
if (x <= mid)
ans += query(id << 1, l, mid, x, y);
if (y > mid)
ans += query(id << 1 | 1, mid + 1, r, x, y);
return ans;
}
int n, m;

signed main() {
n = read(), m = read();
for (register int i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
while (m--) {
int cmd = read();
if (cmd == 1) {
int l = read(), r = read(), k = read();
update(1, 1, n, l, r, k);
}
if (cmd == 2) {
int k = read();
update(1, 1, n, 1, 1, k);
}
if (cmd == 3) {
int k = read();
//cout << "3k:" << k << endl;
update(1, 1, n, 1, 1, -k);
}
if (cmd == 4) {
int l = read(), r = read();
cout << query(1, 1, n, l, r) << endl;
}
if (cmd == 5) {
cout << query(1, 1, n, 1, 1) << endl;
}
//cout << query(1, 1, n, 1, n) << "<---" << endl;
}
return 0;
}