【P3397地毯】二维地毯覆盖计数
一、题目题意
题意说明
有一张 $n \times n$ 的方格地图，铺放了 $m$ 块矩形地毯。每块地毯给出左上角坐标 $(x_1,y_1)$、右下角坐标 $(x_2,y_2)$，整块矩形区域都会被覆盖。最终要求输出整张网格，每个格子上一共被多少块地毯覆盖。
输入输出规则
-
输入格式：
- 第一行两个整数 $n,m$：方格边长、地毯数量
- 接下来 $m$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，代表单块地毯矩形范围
-
输出格式：
- 输出 $n$ 行，每行 $n$ 个数字
- 第 $i$ 行第 $j$ 列代表格子 $(i,j)$ 的覆盖次数
样例演示
输入样例：
5 3
1 1 3 3
2 2 4 4
3 1 5 3
输出样例：
1 1 1 0 0
1 2 2 1 0
2 3 3 2 0
1 2 2 1 0
1 1 1 0 0
样例说明：
- 第一块地毯覆盖 $(1,1)$ 到 $(3,3)$ 的 3×3 区域
- 第二块地毯覆盖 $(2,2)$ 到 $(4,4)$ 的 3×3 区域
- 第三块地毯覆盖 $(3,1)$ 到 $(5,3)$ 的 3×3 区域
- 经过差分标记、前缀和还原后，得到每个格子的覆盖次数，与样例输出完全匹配
二、核心算法：逐行一维差分
1. 一维差分区间修改原理
对一行数组，若要区间 $[L,R]$ 全部 $+1$，仅需两步单点修改：
$$
\text{diff}[L] += 1,\quad \text{diff}[R+1] -= 1
$$
遍历该行做前缀和后，区间内所有数值自动完成 $+1$，单次区间修改复杂度 $O(1)$。
示例：
- 初始数组：
[0, 0, 0, 0, 0] - 对区间
[2,4]加1：diff[2]++,diff[5]-- - 前缀和还原：
[0, 0, 1, 1, 1]
2. 二维矩形转化为逐行差分
题目矩形是 $x\in[x_1,x_2],\ y\in[y_1,y_2]$，等价于：
对每一行 $i \in [x_1,x_2]$，都在该行执行一维区间修改 $[y_1,y_2]$ 加1。
实现方式：
- 循环遍历每一行 $i$（从 $x_1$ 到 $x_2$）
- 在第 $i$ 行的差分标记点执行修改：
a[i][y1]++（区间开始位置）a[i][y2+1]--（区间结束的下一个位置）
全部地毯处理完毕后，对每一行单独做一维前缀和，就能还原出每个格子的覆盖总数。
3. 算法复杂度分析
-
地毯处理阶段：
- 单块地毯最多遍历 $n$ 行
- 总复杂度：$O(m \cdot n)$
-
前缀和还原阶段：
- 遍历 $n \times n$ 网格
- 复杂度：$O(n^2)$
总复杂度：$O(m \cdot n + n^2)$
本题 $n \le 1000$，数据范围完全不会超时。
三、完整 AC 代码
#include <cstdio>
using namespace std;int a[1005][1005]; // 逐行一维差分数组int main() {int n, m;scanf("%d%d", &n, &m);// 处理每块地毯while (m--) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);// 对矩形每一行执行一维差分标记for (int i = x1; i <= x2; i++) {a[i][y1]++; // 区间开始位置 +1a[i][y2 + 1]--; // 区间结束的下一个位置 -1}}// 逐行求前缀和，还原真实覆盖次数并输出for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] += a[i][j - 1]; // 一维前缀和printf("%d ", a[i][j]); // 实时输出}puts(""); // 换行}return 0;
}
四、完整解题步骤
步骤 1：初始化差分二维数组
int a[1005][1005];
- 数组大小 $1005 \times 1005$，适配题目 $n \le 1000$ 的数据范围
- 全局数组自动初始化为 0，无需手动
memset清零 - 本质是把二维网格拆成 $n$ 条独立的一维差分数组，每行单独维护差分标记
步骤 2：读取网格与地毯数量
scanf("%d%d", &n, &m);
读入方格边长 $n$、地毯总数 $m$。
步骤 3：批量处理每一块地毯的区间修改
while (m--) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);for (int i = x1; i <= x2; i++) {a[i][y1]++;a[i][y2 + 1]--;}
}
处理逻辑：
- 循环 $m$ 次读取矩形四角坐标 $x_1,y_1,x_2,y_2$
- 遍历矩形包含的所有行 $i$（$x_1 \le i \le x_2$）
- 在第 $i$ 行的差分标记点执行修改：
a[i][y1]++：区间开始位置标记a[i][y2+1]--：区间结束的下一个位置标记
完成所有地毯处理后，仅存差分标记，还未得到真实覆盖数。
步骤 4：逐行一维前缀和还原答案 + 输出
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] += a[i][j - 1]; // 一维前缀和printf("%d ", a[i][j]); // 实时输出}puts(""); // 换行
}
还原过程：
- 按行遍历网格，每行内部从左到右做前缀和
a[i][j] += a[i][j-1] - 累加后
a[i][j]就是格子 $(i,j)$ 被地毯覆盖的总次数 - 实时打印数值，一行遍历结束后换行
五、代码分段详细讲解
1. 全局差分数组定义
int a[1005][1005];
- 大小设计：题目 $n \le 1000$，但需要访问
y2+1，所以数组大小设为 $1005$ 确保不越界 - 存储含义：
a[i][j]表示第 $i$ 行的一维差分数组在位置 $j$ 的差分值 - 内存占用：$1005 \times 1005 \times 4 \approx 4MB$，完全在限制内
2. 地毯差分标记循环
for (int i = x1; i <= x2; i++) {a[i][y1]++; // 区间开始位置 +1a[i][y2 + 1]--; // 区间结束的下一个位置 -1
}
关键点：
- 矩形覆盖等价于多行一维区间加1
- 对每一行执行标准一维差分两点修改操作
y2+1的减1操作是为了在区间结束后恢复原值
3. 前缀和还原与输出
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] += a[i][j - 1]; // 一维前缀和printf("%d ", a[i][j]); // 实时输出}puts(""); // 换行
}
前缀和原理：
- 差分数组的前缀和就是原数组
- 对于第 $i$ 行：
a[i][j] = a[i][j-1] + diff[j] - 遍历完成后，
a[i][j]就是格子 $(i,j)$ 的最终覆盖次数
六、算法可视化
差分标记过程
flowchart TDA["输入矩形 (x1,y1,x2,y2)"] --> B["遍历每一行 i<br/>从 x1 到 x2"]B --> C["在第 i 行执行<br/>a[i][y1]++"]B --> D["在第 i 行执行<br/>a[i][y2+1]--"]C --> E["继续下一行"]D --> EE --> F{是否处理完所有行?}F -- 否 --> BF -- 是 --> G["继续下一块地毯"]
前缀和还原过程
flowchart TDA["开始还原"] --> B["遍历每一行 i<br/>从 1 到 n"]B --> C["遍历每一列 j<br/>从 1 到 n"]C --> D["计算前缀和<br/>a[i][j] += a[i][j-1]"]D --> E["输出 a[i][j]"]E --> F{是否处理完所有列?}F -- 否 --> CF -- 是 --> G["换行并继续下一行"]G --> H{是否处理完所有行?}H -- 否 --> BH -- 是 --> I["输出完成"]
七、题型总结与拓展
1. 模型定位
- 问题类型：二维矩形区间修改 + 单点查询
- 核心思想：将二维问题分解为多个一维问题
- 适用场景：批量矩形区间增减，最后查询每个点最终数值
2. 两种差分方案对比
| 方案 | 时间复杂度 | 空间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|---|
| 逐行一维差分 | $O(m \cdot n + n^2)$ | $O(n^2)$ | 简单易懂 | $n \le 1000$ 小规模网格 |
| 标准二维差分 | $O(m + n^2)$ | $O(n^2)$ | 稍复杂 | 大数据、大网格效率更高 |
标准二维差分核心操作：
// 二维差分标记
a[x1][y1]++;
a[x1][y2+1]--;
a[x2+1][y1]--;
a[x2+1][y2+1]++;// 二维前缀和还原
for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
3. 核心记忆点
- 矩形拆多行：将二维矩形覆盖转化为对每一行的一维区间操作
- 一维差分标记：每行使用
[L,R]一维差分标记（diff[L]++,diff[R+1]--） - 逐行前缀和：最后对每一行单独做前缀和还原真实值
- 边界处理：注意
y2+1的减1操作，防止数组越界
4. 常见变式
- 多次修改后查询：本题是修改后立即查询，如果中间有多次修改和查询交替，需要维护差分数组
- 带权覆盖：每块地毯有不同的权重值，修改时不是加1而是加权重值
- 三维扩展：扩展到三维空间，使用三维差分或逐层二维差分