我将 LeetCode 1314 题改写为了标准的 NOI/CSP 普及组/提高组风格题目。

本题是二维前缀和的进阶应用：从“查询任意矩形”转变为“对每个点都查询其周围固定范围的矩形”。

[OI 基础训练] 能量采集器 (矩阵区域和)

一、 题目背景与知识点讲解

在学习了二维前缀和的基本查询后，我们来看一个更实际的应用场景。

场景描述： 你需要处理一个 $N \times M$ 的矩阵。与上一题（处理 $Q$ 次任意询问）不同，这次我们需要对矩阵中的每一个位置，都计算以它为中心，向外延伸 $K$ 格的矩形区域内的元素之和。

1. 问题分析

• 朴素暴力法： 对于矩阵中的每一个点 $(i, j)$，都写两个循环，遍历从 $i-K$ 到 $i+K$，以及 $j-K$ 到 $j+K$ 的范围累加。

  • 每个点计算耗时：$O(K^2)$
  • 总点数：$N \times M$
  • 总复杂度：$O(N \cdot M \cdot K^2)$。当 $N, M, K$ 均达到 $1000$ 级别时，计算量爆炸，必然超时。

• 前缀和优化： 既然是求矩形区域的和，这正是二维前缀和的看家本领。 虽然查询的位置变了（变成了以每个点为中心的滑动窗口），但核心依然是子矩阵求和。

  • 预处理：$O(N \cdot M)$ 计算出二维前缀和数组 S。
  • 查询：对于每个点 $(i, j)$，算出其管辖的矩形左上角 $(r_1, c_1)$ 和右下角 $(r_2, c_2)$，然后用 $O(1)$ 公式计算。
  • 总复杂度：$O(N \cdot M)$，完美解决。

2. 核心难点：坐标边界计算 对于中心点 $(i, j)$ 和半径 $K$：

• 理想情况：
  • 左上角：$(i - K, j - K)$
  • 右下角：$(i + K, j + K)$
• 实际情况（边界处理）： 题目要求不能越出矩阵边界。因此我们需要取交集：
  • 左上角行号 $r_1 = \max(1, i - K)$
  • 左上角列号 $c_1 = \max(1, j - K)$
  • 右下角行号 $r_2 = \min(N, i + K)$
  • 右下角列号 $c_2 = \min(M, j + K)$

二、 题目描述

在一个 $N \times M$ 的网格地图上，分布着不同强度的能量源。网格 $(i, j)$ 处的能量强度为 $A_{i,j}$。

现在，我们需要在每一个格子上都放置一个“能量采集器”。 位于 $(i, j)$ 的采集器可以收集以它为中心，向上下左右各延伸 $K$ 格的矩形区域内（包含中心本身）的所有能量。

具体来说，对于位置 $(i, j)$ 的采集器，它可以收集所有满足以下条件的 $(r, c)$ 处的能量：

且 $(r, c)$ 必须在地图范围内。

请你生成一个新的矩阵，其中第 $i$ 行第 $j$ 列的数值表示该位置采集器收集到的总能量。

注意： 本题采用 1-based 索引（行号列号从 1 开始）。

输入格式

第一行包含三个整数 $N, M, K$，分别表示地图的行数、列数和采集范围半径。 接下来 $N$ 行，每行包含 $M$ 个整数，表示能量矩阵 $A$。

输出格式

输出 $N$ 行，每行 $M$ 个整数，表示结果矩阵。每个整数之间用一个空格隔开。

数据范围

• $1 \le N, M \le 1000$
• $0 \le K \le 1000$
• $1 \le A_{i,j} \le 100$
• 结果保证在 32 位有符号整数范围内（但在 OI 中建议使用 long long）。

样例输入

3 3 1
1 2 3
4 5 6
7 8 9

样例输出

12 21 16
27 45 33
24 39 28

样例解释

• 位置 (1, 1)，$K=1$： 范围是左上(0,0)到右下(2,2)。修正边界后为左上(1,1)到右下(2,2)。 覆盖元素：1, 2, 4, 5。和为 $1+2+4+5 = 12$。
• 位置 (2, 2)，$K=1$： 范围是左上(1,1)到右下(3,3)。全图覆盖。 和为 $1+2+3+4+5+6+7+8+9 = 45$。

三、 标准代码 (C++14 OI风格)

见题解

四、 教学备课重点 (教练参考)

1. 从“点”到“面”的思维转换：

   • 学生可能习惯了“给定一个查询列表”的题目形式。本题没有显式的“查询列表”，而是隐含在“对每个点都算一次”的要求中。
   • 需要引导学生意识到：这本质上就是进行了 $N \times M$ 次前缀和查询，只是查询的坐标是动态计算的。

2. 边界计算的鲁棒性：

   • 本题最容易写出的 Bug 是数组越界。
   • 例如：直接写 s[i+k][j+k] 会导致访问越界；写 s[i-k-1][...] 当 i-k-1 < 0 时也会越界。
   • 教学技巧：画图演示。当中心点在矩阵角上时，它的采集范围有一部分是“虚空”的。在代码中通过 max(1, ...) 和 min(N, ...) 将“虚空”范围裁剪到矩阵的物理边缘。

3. 时间复杂度对比：

   • 让学生计算：如果 $N=1000, M=1000, K=500$。
   • 暴力法：每个点要加 $1000 \times 1000$ 次，总共 $10^6 \times 10^6 = 10^{12}$ 次运算 $\to$ 死机/超时。
   • 前缀和法：预处理 $10^6$，查询 $10^6$ 次 $O(1)$，总共约 $2 \times 10^6$ 次运算 $\to$ 0.01秒。
   • 这种巨大的反差能给学生留下深刻印象。

4. 空间优化（进阶）：

   • 本题需要输出一个新矩阵。如果直接输出，可以不存储结果矩阵，算一个打印一个。
   • 如果内存限制极严，s 数组和 mat 数组可以合并吗？
     • 可以复用。读入时直接计算 s，不需要保存原始 mat（除非后续还要用到单点值，但本题不需要）。这样可以节省一半空间。