P2367 语文成绩
暴力模拟过不了，时间复杂度是 \(\operatorname O(n^2)\)。
差分思想
- 对于数组 \(a\)，定义 \(a\) 的差分数组为 \(b\)，其中 \(b_1 = a_1, b_i = a_i - a_{i - 1}(2\leq i\leq n)\)
| \(i\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(a_i\) | 1 | 1 | 2 | 2 | 1 | 3 | 3 | 5 |
| \(b_i\) | 1 | 0 | 1 | 0 | -1 | 2 | 0 | 2 |
-
对数组 \(b\) 求前缀和：
\[\sum_{i = 1}^n b_i = a_1 + \sum_{i = 2}^n(a_i - a_{i - 1}) = \sum_{i =1}^n a_i - \sum_{i = 1}^{n-1}a_i = a_n \] -
可以发现
-
若将 \(b_x\) 增加 \(1\)，再对 \(b\) 数组求前缀和得到 \(a\) 数组，那么得到的 \(a\) 数组中 \(a_x, a_{x+1},\dots ,a_n\) 均增加 \(1\)。
-
若将 \(b_y\) 减少 \(1\)，再对 \(b\) 数组求前缀和得到 \(a\) 数组，那么得到的 \(a\) 数组中 \(a_y, a_{y+1},\dots ,a_n\) 均减少 \(1\)。
-
例如，对于一个全为 \(0\) 的差分数组 \(b\)，若将 \(b_3\) 增加 \(1\)，将 \(b_6\) 减少 \(1\)，得到的 \(a\) 数组如表所示：
\(i\) 1 2 3 4 5 6 7 8 \(b_i\) 0 0 +1 0 0 -1 0 0 \(a_i\) 0 0 1 1 1 0 0 0
-
-
因此，将 \(a\) 数组中第 \(x\) 元素到第 \(y\) 元素增加 \(z\) 的修改操作，可以转化为将 \(b_x\) 增加 \(z\)，\(b_{y + 1}\) 减少 \(z\)，最后再对 \(b\) 数组求前缀和。
-
这样，对于每次修改操作，只需要修改 \(2\) 个点，时间复杂度变为 \(\operatorname O(1)\)。
-
同时，因为只有在最后一次修改操作才需要得到 \(a\) 数组的具体值，所以只需要所有修改操作结束后求一次前缀和即可。
代码实现
#include<iostream>
#include<algorithm>
#include<cstdio>
const int N = 5e6 + 10;
int n, m, x, y, z, a[N], b[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n >> m;
for (int i = 1; i <= n; i++) std::cin >> a[i], b[i] = a[i] - a[i - 1];
for (int i = 1; i <= m; i++)
{
std::cin >> x >> y >> z; b[x] += z, b[y + 1] -= z;
}
int min = 0x7fffffff;
for (int i = 1; i <= n; i++)
{
b[i] += b[i - 1]; min = std::min(min, b[i]);
}
std::cout << min;
return 0;
}