AcWing 99. 激光炸弹

题目链接：99. 激光炸弹 - AcWing题库

观察 $S[i, j], S[i - 1, j], S[i, j - 1], S[i - 1, j - 1]$ 的关系。

容易得到如下的递推式：

\[S[i, j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j]\]

同理，对于任意一个边长为 $R$ 的正方形，我们有：

\[\sum_{x = i - R + 1}^i \sum_{y = j - R + 1}^j{A[x, y] = S[i, j] - S[i - R, j] - S[i, j - R] + S [i - R, j - R]}\]

因此，我们只需要 $\mathcal{O}(N^2)$ 递推求出二维前缀和 $S$，

然后 $\mathcal{O}(N^2)$ 枚举边长为 $R$ 的正方形的右下角坐标 $(i, j)$，

即可通过上式 $\mathcal{O}(1)$ 计算出该正方形内所有目标的价值之和，更新答案。

上面给出的两个式子蕴含的思想其实就是 “容斥原理”。

上面我们吧 $(X_i, Y_i)$ 作为一个 “格子”，

而原题中 $(X_i, Y_i)$ 是一个点，

并且正方形边上的目标不会被摧毁。

实际上，我们不妨认为这个点就处于 “格子” $(X_i, Y_i)$ 的中心位置，

格子的左上角坐标为 $(X_i - 0.5, Y_i - 0.5)$，

右下角坐标为 $(X_i + 0.5, Y_i + 0.5)$，

而正方形的右下角处于 “格线交点” 上，

即一个值为 “□.5” 的坐标。

这个转化与原问题是等价的。

另外，本题内存限制较为严格，

我们可以省略 $A$ 数组，

读入时直接向 $S$ 中累加。

完整代码：激光炸弹.cpp