2362. 区间修改（减法）与最值查询
1000ms
256MB
简单
前缀和与差分
题目描述
某校期中考试结束后采用阅卷机阅卷。老师在检查成绩时发现阅卷机阅卷有误，因此需要手动调整同学们的成绩。
现有 $n$ 个同学的初始成绩，需要进行 $p$ 次调整。每次调整操作将第 $x$ 个同学到第 $y$ 个同学（包含第 $x$ 个和第 $y$ 个同学）的成绩每人减去 $z$ 分。
请问在所有调整操作完成后，全班同学的最高分是多少分？
输入格式
- 第一行包含两个正整数 $n$ 和 $p$ ($1 \le n \le 100000, \quad 1 \le p \le n$)，分别代表学生人数和减少分数的次数。
- 第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 100$)，代表每个学生的初始成绩。
- 接下来 $p$ 行，每行包含三个整数 $x, y, z$ ($1 \le x \le y \le n, \quad 0 \le z \le 100$)，代表给第 $x$ 个同学到第 $y$ 个同学每人减少 $z$ 分。
输出格式
- 输出一行一个整数，代表修改分数后全班的最高分。
样例 1
输入 (Input)
3 2 5 5 4 1 2 1 2 3 1
输出 (Output)
4
- 对于 $100\%$ 的数据：$n \le 100000$，$p \le n$，$1 \le x \le y \le n$，$0 \le a_i, z \le 100$。
- **算法提示**：
由于涉及多次区间修改与一次最终的全局最值查询，可以使用**差分数组**在 $O(1)$ 的单次时间复杂度内完成区间修改：
1. 设差分数组为 $D$，初始时 $D$ 的所有元素为 0。
2. 对于每次区间修改操作，将区间 $[x, y]$ 内的每个数减去 $z$，只需对差分数组进行两点更新：
- $D[x] \leftarrow D[x] - z$
- $D[y+1] \leftarrow D[y+1] + z$
3. 所有修改操作完成后，计算差分数组的前缀和并加回原数组 $a[i]$，即可还原出调整后的成绩，最后遍历寻找最大值。
4. 这种方法使单次修改的时间复杂度降低至 $O(1)$，整体时间复杂度为 $O(N + P)$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功