题解 P2280 【[HNOI2003]激光炸弹】
iMya_nlgau
·
·
题解
题解 [HNOI2003] 激光炸弹
- 2022/4/29 upd：几乎重写了一遍，改了一下码风，讲的更清楚了些。
可能会更好的阅读体验
这道题要用到一个重要的基础算法——前缀和（二维）
众所周知，对于一个序列 A，我们可以通过递推求出它的前缀和序列 S：
S_i=\sum\limits_{j=1}^iA_j
然后就可以 O(1) 求出子段和
\sum\limits_{i=l}^rA_i=S_r-S_{l-1}
对于这道题，我们也希望能在 O(1) 的时间内求出一个正方形区域的部分和，这就要用到二维前缀和。
二维前缀和
类比一维前缀和，我们定义 A 的二维前缀和 S：
S_{i,j}=\sum\limits_{x=1}^i\sum\limits_{y=1}^jA_{x,y}
那么如和递推求出 $S$ 呢？ 通常的方法有以下两种：
#### 方法一
我们来观察下图：
简单地应用容斥原理的思想，可以得到以下递推式：
$$
S_{i,j}(\text{整个矩形})=S_{i-1,j}(\text{红色+绿色部分})+S_{i,j-1}(\text{红色+浅蓝色部分})
$$
$$
-S_{i-1,j-1}(\text{红色部分})+A_{i,j}(\text{深蓝色部分})
$$
这样我们就可以 $O(n^2)$ 预处理出二维前缀和 $S$。代码如下：
```cpp
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
// a[i][j] 为原二维数组（下标范围 1~n）
// s[i][j] 为二维前缀和的结果
```
#### 方法二
我们考虑先对每一行求出一维前缀和，这时得到的 $S^\prime_{i,j}$ 实际上表示的是第 $i$ 行，前 $j$ 个位置的和。然后我们再对 $S^\prime$ 的每一列做一遍一维前缀和，这次得到的 $S_{i,j}$ 就是前 $i$ 行每行前 $j$ 个位置和的加和，也就是 $(i,j)$ 左上这一矩形区域的和了，即我们要的二维前缀和。复杂度仍然是 $O(n^2)$。
代码如下：
```cpp
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) s[i][j] = s[i][j - 1] + a[i][j];
for (int j = 1; j <= n; j ++)
for (int i = 1; i <= n; i ++) s[i][j] += s[i - 1][j];
```
两种方法比较一下，方法一有一个劣势，可以注意到，它的递推式中总共有 $4$ 项，如果再类比到三维前缀和，采用同样容斥思想，递推式中就总共有 $8$ 项。一般地，采用容斥计算 $k$ 维前缀和的复杂度为 $O(2^k n^k)$ 当 $k$ 较大时 $2^k$ 就是一个很大的常数因子了，而方法二扩展到 $k$ 维的复杂度为 $O(kn^k)$。在高维前缀和（一般用来求解子集和问题，即对所有 $0\leq i<2^k$ 求解 $\sum_{j\subseteq i}a_j$）中会用到方法二的思想。不过一般的问题中（比如这题），两种方法都没有任何问题。
下面考虑查询，及如何通过二维前缀和数组得到一个矩形区域的部分和。这是容易 $O(1)$ 做到的。
同样采用容斥思想（读者可以仿照上面方法一的图理解一下）以 $(i,j)$ 为右下角，长为 $R$，宽为 $C$ 的矩形区域的部分和即为
$$
\sum\limits_{x=i-C+1}^i\sum\limits_{y=j-R+1}^jA_{x,y}= S_{i,j}-S_{i-C,j}-S_{i,j-R}+S_{i-C,j-R}
$$
至此，我们可以 $O(n^2)$ 地预处理出二维前缀和 $S$，再枚举所有边长 $m$ 的正方形区域，得到最大值即本题答案。
该算法的时间复杂度和空间复杂度都是 $O(n^2)$，本题 $n\leq 5000$，就做完了。
注意，以上我写的 $n$ 指的是坐标范围而非题面中的目标个数。
### 本题一些实现上的细节
- 虽然题目保证结果不会超过 $32767$，但中间过程可能超出 $\texttt{short}$ 的范围，所以仍需使用 $\texttt{int}$。（我之前用的 $\texttt{short}$ 却 AC 了，就很玄学）
- 我们可以把每个坐标看成在一个小正方形区域中间而非一个点（即横纵坐标加 $0.5$），就可以发现并不需要对恰好在正方形边上的点特殊处理。
- 为了防止越界，要把横纵坐标都加一。
下面是 AC 代码：
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, s[5010][5010];
// 因为空间较为紧张，这里只用了一个数组，计算出前缀和后原数组直接被覆盖
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
int x, y, v;
cin >> x >> y >> v;
s[x + 1][y + 1] += v; // 将横纵坐标都加一，坐标范围变成 [1, 5001]，避免越界
}
int N = 5001; // N 为坐标范围
// 方法一
for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j ++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
/*
// 方法二
for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j ++) s[i][j] += s[i][j - 1];
for (int j = 1; j <= N; j ++)
for (int i = 1; i <= N; i ++) s[i][j] += s[i - 1][j];
*/
int ans = 0;
for (int i = m; i <= N; i ++)
for (int j = m; j <= N; j ++) {
int num = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];
// num 为以 (i, j) 为右下角的边长为 m 的正方形区域中的目标价值之和
ans = max(ans, num);
// 用 num 更新答案
}
cout << ans << endl;
return 0;
}
```
作为扩展，再讲一下与二维前缀和对应的二维差分（下面内容已与本题无关）
### 二维差分
在一维上，我们知道前缀和的逆过程，差分。另 $B_i=A_i-A_{i-1}$，那么 $B$ 就称作 $A$ 的差分，容易发现，对差分序列求前缀和得到的就是原序列，而对前缀和序列求差分也能得到原序列。前缀和与差分类似积分与微分，只不过前者应用于离散的（序列），后者应用于连续的（函数）。
而差分在题目中的应用也是及其广泛的，最基本的应用就是对序列进行多次区间修改（加一个数），最后询问最终序列。将序列 $A$ 的 $[l,r]$ 区间加上一个数 $v$，考察它的差分序列 $B$，发现 $B_{l}$ 增加了 $v$，而 $B_{r+1}$ 减少了 $v$。所以我们可以维护差分序列，修改操作是 $O(1)$ 的，最后求一遍前缀和就得到原序列。
考虑扩展到二维的情况，我们想处理对二维数组中一个矩形区域加一个数的操作，我们也可以类比出二维差分。与二维前缀和一样，也有两种理解方法。
#### 方法一
因为差分是前缀和的逆运算，所以原数组 $A$ 就是其差分 $B$ 的前缀和，根据上文讲的根据二维前缀和求部分和，那么 $B_{i,j}$ 就等于 $A_{i,j}-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1}$。
而考虑对 $A$ 中左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$ 的矩形区域加上 $v$，考察 $B$ 的变化，我们发现 $B_{x_1,y_1}$ 增加了 $v$，$B_{x_2+1,y_1}$ 减小了 $v$，$B_{x_1,y_2+1}$ 减小了 $v$，$B_{x_2+1,y_2+1}$ 增加了 $v$。于是我们就可以每次操作 $O(1)$ 地维护 $B$，最后求一遍二维前缀和得到 $A$ 的最终结果。
#### 方法二
与方法一相比，我更喜欢的是这个方法，感觉跟清楚一些。
还是考虑对 $A$ 中左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$ 的矩形区域加上 $v$，我们不妨先对每一行做一维差分，那么一次矩形加操作就给 $x_1$ 到 $x_2$ 每一行的 $y_1$ 位置加上 $v$，$y_2+1$ 位置减去 $v$，如下图所示：
（红色矩形内所有位置加 $v$）
现在我们竖着观察这个操作，发现相当于给第 $y_1$ 和 $y_2+1$ 列各进行了一次区间加（减）操作，这是我们已经用一维差分解决的问题。所以我们再竖着对每一列做一遍差分，就做完了。
这个方法甚至可以扩展到给一个直角三角形区域加一个数的操作（直角边与坐标轴平行），依然是对每一行差分，问题就变成了对竖着一列的一段区间加（减）一个数，和对斜着的一段区间加（减）一个数，我们竖着和斜着再差分就可以了。
习题 [P8228 「Wdoi-5」模块化核熔炉](https://www.luogu.com.cn/problem/P8228)，这个题是对六边形区域的修改操作，不过做法是类似的。
前缀和与差分是及其重要的基础算法，应用也非常广泛，本文只是其最基本的应用。考虑到很多读者可能是刚开始学习算法，前缀和与差分也能帮助建立复杂度的思想（多次区间查询，我们采用 $O(n)$ 预处理 $O(1)$ 查询的前缀和，若多次区间修改，便采用维护差分 $O(1)$ 修改的方法）。
如果感觉讲的还清楚就点个赞再走吧（卑微求赞）