P12810 矩阵矩形边界差分法高效解法与 C++ 实现

这个问题要求高效地处理矩形边界加1的多次操作，最终输出整个矩阵。直接模拟每个操作会超时，因为 `n*m` 可达 4,000,000，`q` 可达 1,000,000。 ## 🔍 解题思路 我们需要使用**差分数组（差分矩阵）**来优化。 ### 📐 核心思想 每次操作是给一个矩形的**边界**加1。我们可以通过： - 给整个矩形区域加1（使用二维差分） - 再给内部区域减1（去掉非边界部分） 这样等价于只给边界加1。 ### 💡 具体公式 对于每个操作 `(x1, y1, x2, y2)`： 1. 首先对整个矩形区域加1： - `diff[x1][y1] += 1` - `diff[x1][y2+1] -= 1` - `diff[x2+1][y1] -= 1` - `diff[x2+1][y2+1] += 1` 2. 然后对内部区域（即 `(x1+1, y1+1)` 到 `(x2-1, y2-1)`）减1： - `diff[x1+1][y1+1] -= 1` - `diff[x1+1][y2] += 1` - `diff[x2][y1+1] += 1` - `diff[x2][y2] -= 1` ⚠️ **注意**：内部区域可能不存在（当 `x1+1 > x2-1` 或 `y1+1 > y2-1`），即矩形至少有一行或一列时不需要减去内部区域。 ### 📊 时间复杂度 - 每个操作修改差分数组的常数个位置：O(1) - 最后对差分数组做前缀和：O(n*m) - 总复杂度：O(q + n*m) ≈ 1,000,000 + 4,000,000 = 5,000,000，远小于限制。 --- ## 💻 C++ 实现 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 2005; int diff[MAXN][MAXN]; // 差分数组 int main() { freopen("rectangle.in", "r", stdin); freopen("rectangle.out", "w", stdout); int n, m, q; scanf("%d %d %d", &n, &m, &q); while (q--) { int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); // 1. 对整个矩形区域加1 diff[x1][y1] += 1; diff[x1][y2+1] -= 1; diff[x2+1][y1] -= 1; diff[x2+1][y2+1] += 1; // 2. 对内部区域减1（仅当内部存在） if (x1+1 <= x2-1 && y1+1 <= y2-1) { diff[x1+1][y1+1] -= 1; diff[x1+1][y2] += 1; diff[x2][y1+1] += 1; diff[x2][y2] -= 1; } } // 计算前缀和 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]; printf("%d ", diff[i][j]); } printf("\n"); } return 0; } ``` --- ## 📝 关键点解析 ### 🧮 二维差分公式 对于矩形叠加和问题，标准方法是： 1. 修改 `(x1,y1)` 处 +v，`(x1,y2+1)` 处 -v，`(x2+1,y1)` 处 -v，`(x2+1,y2+1)` 处 +v 2. 最终对该二维数组按行做前缀和（先按行，再按列或同时） ### ⚠️ 边界情况 1. **索引越界**：差分数组大小至少为 `(n+2)*(m+2)`，确保 `x2+1` 和 `y2+1` 不越界。 2. **单行或单列矩形**：内部区域不存在，不需要减内部，实现时用 `if` 判断。 3. **输出效率**：使用 `printf`/`scanf` 比 `cin`/`cout` 快。 --- ## 🧪 验证样例 输入样例： ``` 4 4 2 1 1 3 4 1 2 4 4 ``` 我们的代码输出： ``` 1 2 2 2 1 1 0 2 1 2 1 2 0 1 1 1 ``` 与题目样例完全一致 ✅ --- ## 💡 开发建议 1. **内存优化**：如果 `n`、`m` 最大为 2000，则数组大小 `2005 * 2005` 约 4MB int，完全可接受（内存限制 512MB）。 2. **常使用 `const int` 定义最大值**，避免魔法数字。 3. **文件操作**：记得 `freopen` 且使用标准输入输出函数。 4. **考虑大输入**：`q` 最大 10^6，务必使用快速 I/O。 5. **多测试**：可传入多组数据确保边界情况正确。 ######[AI写代码神器 | 1332点数解答 | 2026-08-20 20:16:44]