2514 【基础】倒水Ⅱ
大约 4 分钟
2514 【基础】倒水Ⅱ
【算法】 二阶差分(等差数列差分)
【C++】 差分数组、二阶差分、一维数组、long long
【难度】 普及/提高−
一、题目简述
有 个杯子,每个杯子初始有一些水。进行 次倒水操作(),每次操作向区间 内的杯子加入一个等差数列:第 杯加 ,第 杯加 ,第 杯加 ,……,第 杯加 (其中 )。求所有操作结束后每个杯子的水量。
二、解题思路
2.1 问题分析
这是经典的区间加等差数列问题。普通差分只能处理"区间加同一个值",而这里每次加的是一个等差数列,需要二阶差分来解决。
2.2 从一阶差到二阶差
回顾:一阶差分数组 。如果要对 统一加 ,只需 b[L] += x; b[R+1] -= x,最后对 做一次前缀和即可还原。
现在要对 加上 ,考虑这个等差数列的一阶差分长什么样:
- 第 项比前一项多 (前一项不加),所以
- 第 项比第 项多 ,所以
- 第 项比第 项多 ,所以
- ……
- 第 项比第 项多 ,所以
- 第 项比第 项少 (等差数列结束),所以
也就是说,一阶差分的变化是:
b[L] += s
b[L+1..R] += d(中间每个位置加 d)
b[R+1] -= e其中 b[L+1..R] += d 又是一个区间加常数问题!对 再做一次差分(即对 做二阶差分)就能 处理。
2.3 二阶差分公式
设二阶差分数组 。对上述 的修改,反映到 上:
b[L] += sc[L] += s,c[L+1] -= s- 对于 :
b[i] += dc[L+1] += d,c[R+1] -= d b[R+1] -= ec[R+1] -= e,c[R+2] += e
合并同类项后,一次操作只需修改二阶差分数组的 4 个位置:
c[L] += s
c[L+1] += d - s
c[R+1] += -e - d
c[R+2] += e2.4 还原答案
所有操作处理完后,对二阶差分数组 做两次前缀和即可还原出每个位置的增量:
- 第一次前缀和:,此时 变成一阶差分
- 第二次前缀和:,此时 变成每个位置的实际增量
- 将增量加到原数组 上,输出即可
2.5 手动模拟
假设 ,初始水量全为 0。一次操作:,则 。
等差数列:。
二阶差分修改:
c[2] += 3
c[3] += 2 - 3 = -1
c[5] += -7 - 2 = -9
c[6] += 7数组 变为:
第一次前缀和后:(这就是一阶差分 )
第二次前缀和后(取前 5 位):(这就是每个位置的增量)✅
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long a[N]; // 初始水量,最终存答案
long long c[N]; // 二阶差分数组
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (k--) {
int L, R, s, e, d;
cin >> L >> R >> s >> e >> d;
c[L] += s;
c[L + 1] += d - s;
c[R + 1] += -e - d;
c[R + 2] += e;
}
// 第一次前缀和:c 变为一阶差分
for (int i = 1; i <= n; i++) {
c[i] += c[i - 1];
}
// 第二次前缀和 + 加到原数组并输出
for (int i = 1; i <= n; i++) {
c[i] += c[i - 1];
a[i] += c[i];
cout << a[i] << " \n"[i == n];
}
return 0;
}四、复杂度分析
- 时间复杂度:。每次操作 修改 4 个位置,最后两次 前缀和还原。
- 空间复杂度:。需要两个长度为 左右的
long long数组。
五、易错点
- 数组越界:二阶差分会访问到
R+2,数组要开到 以上。 - 数据类型:,累加后可能超过
int范围,必须用long long。 - 二阶差分的理解: 表示"一阶差分的变化量"。建议在纸上手动模拟一组小数据,理解 4 个修改位置的含义。
- 公式推导: 处加了 而不是 ,容易漏掉 这一项。
