题意描述
洛谷链接
\(N\)
个柱子排成一排，一开始每个柱子损伤度为 0。
接下来勇仪会进行 \(M\)
次攻击，每次攻击可以用 4 个参数\(l\),\(r\),\(s\),\(e\)来描述：
表示这次攻击作用范围为第 \(l\)
个到第 \(r\) 个之间所有的柱子（包含
\(l\)，\(r\)），对第一个柱子的伤害为 \(s\)，对最后一个柱子的伤害为 \(e\)。
攻击产生的伤害值是一个等差数列。若 \(l =
1\)，\(r = 5\)，\(s = 2\)，\(e =
10\)，则对第 1 ~ 5 个柱子分别产生 2, 4, 6, 8, 10 的伤害。
鬼族们需要的是所有攻击完成之后每个柱子的损伤度。
解题思路
一道简单但比较有意思的思维题。
我们可以考虑构造一个差分序列 \(\text{diff1}\)，显然对于公差为 \(d\) 等差数列 \(a_{l \cdots r}\)，\(\text{diff1}_{l + 1 \cdots r} =
d\)，但此时对于添加一个等差数列，对于 \(\text{diff1}\) 的操作仍然是 \(O(n)\) 的。此时我们可以考虑对 \(\text{diff1}\) 再构造一个差分序列 \(\text{diff2}\)。对于上述的等差数列，我们仅需要在
\(\text{diff2}_l = a_l\)，\(\text{diff2}_{l + 1} = d - a_l\)，\(\text{diff2}_{r + 1} = - d - a_r\)，\(\text{diff2}_{r + 2} = a_r\)
即可，对于单个等差数列把算法优化到 \(O(1)\)。
代码演示
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 10000000;
int main() {
int n, m;
scanf("%d %d", &n, &m);
static long long diff2[MAXN + 3];
memset(diff2, 0, sizeof(diff2));
for (int i = 0; i < m; i++) {
int l, r;
long long s, e;
scanf("%d %d %lld %lld", &l, &r, &s, &e);
if (l == r) {
diff2[l] += s;
diff2[r + 1] -= s + e;
diff2[r + 2] += e;
} else {
long long d = (e - s) / (r - l);
diff2[l] += s;
diff2[l + 1] -= s - d;
diff2[r + 1] -= e + d;
diff2[r + 2] += e;
}
}
static long long diff[MAXN + 1];
diff[0] = 0;
for (int i = 1; i <= n; i++) {
diff[i] = diff2[i] + diff[i - 1];
}
long long sumXor = 0, maxN = 0, each = 0;
for (int i = 1; i <= n; i++) {
each += diff[i];
sumXor ^= each;
maxN = std::max(maxN, each);
#ifdef DBG
printf("%lld ", each);
#endif
}
#ifdef DBG
putchar('\n');
#endif
printf("%lld %lld\n", sumXor, maxN);
return 0;
}
|