语文成绩

题意

有 n 个学生，每个学生有一个初始语文成绩。

接下来有 p 次修改，每次给出 l r z，表示把第 l 到第 r 个学生的成绩都增加 z。

要求输出所有修改完成后，全班最低的语文成绩。

思路

先看一个可以直接验证想法的朴素解：

cpp

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

int a[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p;
    cin >> n >> p;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= p; i++) {
        int l, r, z;
        cin >> l >> r >> z;
        // 朴素做法：把区间里的每个学生成绩都加上 z。
        for (int j = l; j <= r; j++) {
            a[j] += z;
        }
    }

    int ans = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] < ans) ans = a[i];
    }

    cout << ans << '\n';
    return 0;
}

朴素做法每次修改都枚举 [l,r] 中的所有学生。它很容易理解，但 n 和 p 都可能达到 5 * 10^6，最坏情况下无法通过。

这题的操作都是“连续区间整体加一个数”，并且中间没有查询，最后才求结果。按照 rbook《差分》文章中的模型，这正是普通差分适用的场景。

设差分数组为：

text

1diff[i] = a[i] - a[i-1]

如果要让 [l,r] 每个数都加 z，只需要：

text

1
2diff[l] += z
diff[r+1] -= z

因为前缀和还原时，从 l 开始都会多累加到 z，从 r+1 开始这个 z 又被抵消。

一次修改的影响

这张表展示一次 [l,r] 加 z 对不同位置的影响。

位置范围	前缀和中是否包含 `+z`	前缀和中是否包含 `-z`	最终变化
`i < l`	否	否	不变
`l <= i <= r`	是	否	增加 `z`
`i > r`	是	是	抵消，不变

读入初始成绩时，也可以把第 i 个成绩看成一次 [i,i] 的区间加法，直接写进同一个差分数组。

最后从左到右做前缀和还原每个学生的最终成绩，同时维护最小值即可。

Python 知识

array("i") 用连续的 32 位整数保存五百万项差分，避免 Python list[int] 的对象开销。
os.read 分块解析整数，不会让超长输入行的 split() 瞬间创建数百万个字节串。
islice(difference, n) 只遍历有效部分，不复制大数组。

代码

python

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
46import os
from array import array
from itertools import islice


def read_ints():
    number = 0
    sign = 1
    reading = False
    while chunk := os.read(0, 1 << 20):
        for byte in chunk:
            if 48 <= byte <= 57:
                number = number * 10 + byte - 48
                reading = True
            else:
                if reading:
                    yield sign * number
                    number = 0
                    sign = 1
                    reading = False
                elif byte == 45:
                    sign = -1
    if reading:
        yield sign * number


data = iter(read_ints())
n, operations = next(data), next(data)
difference = array("i", [0]) * (n + 1)
previous = 0
for i in range(n):
    score = next(data)
    difference[i] = score - previous
    previous = score

for _ in range(operations):
    left, right, change = next(data), next(data), next(data)
    difference[left - 1] += change
    difference[right] -= change

score = 0
answer = 1 << 60
for change in islice(difference, n):
    score += change
    answer = min(answer, score)
print(answer)

复杂度

建立差分数组需要 $O(n)$ 。
每次修改只改两个端点，p 次修改需要 $O(p)$ 。
最后还原并求最小值需要 $O(n)$ 。
总时间复杂度 $O(n + p)$ 。
空间复杂度 $O(n)$ 。

总结

这题是“一维差分”的直接应用。

看到大量区间加法，并且所有操作结束后才查询最终结果，就应该先想到差分。差分的作用是把一次区间修改压缩成两个端点修改，最后再用一次前缀和把所有影响还原出来。

目录

题意

思路

一次修改的影响

Python 知识

代码

复杂度

总结