【P3397地毯】二维地毯覆盖计数

一、题目题意

题意说明

有一张 $n \times n$ 的方格地图，铺放了 $m$ 块矩形地毯。每块地毯给出左上角坐标 $(x_1,y_1)$、右下角坐标 $(x_2,y_2)$，整块矩形区域都会被覆盖。最终要求输出整张网格，每个格子上一共被多少块地毯覆盖。

输入输出规则

1. 输入格式：

   • 第一行两个整数 $n,m$：方格边长、地毯数量
   • 接下来 $m$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，代表单块地毯矩形范围

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。

实现方式：

1. 循环遍历每一行 $i$（从 $x_1$ 到 $x_2$）
2. 在第 $i$ 行的差分标记点执行修改：
   • a[i][y1]++（区间开始位置）
   • a[i][y2+1]--（区间结束的下一个位置）

全部地毯处理完毕后，对每一行单独做一维前缀和，就能还原出每个格子的覆盖总数。

3. 算法复杂度分析

1. 地毯处理阶段：

   • 单块地毯最多遍历 $n$ 行
   • 总复杂度：$O(m \cdot n)$

2. 前缀和还原阶段：

   • 遍历 $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]--;}
}

处理逻辑：

1. 循环 $m$ 次读取矩形四角坐标 $x_1,y_1,x_2,y_2$
2. 遍历矩形包含的所有行 $i$（$x_1 \le i \le x_2$）
3. 在第 $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("");  // 换行
}

还原过程：

1. 按行遍历网格，每行内部从左到右做前缀和 a[i][j] += a[i][j-1]
2. 累加后 a[i][j] 就是格子 $(i,j)$ 被地毯覆盖的总次数
3. 实时打印数值，一行遍历结束后换行

五、代码分段详细讲解

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. 核心记忆点

1. 矩形拆多行：将二维矩形覆盖转化为对每一行的一维区间操作
2. 一维差分标记：每行使用 [L,R] 一维差分标记（diff[L]++, diff[R+1]--）
3. 逐行前缀和：最后对每一行单独做前缀和还原真实值
4. 边界处理：注意 y2+1 的减1操作，防止数组越界

4. 常见变式

1. 多次修改后查询：本题是修改后立即查询，如果中间有多次修改和查询交替，需要维护差分数组
2. 带权覆盖：每块地毯有不同的权重值，修改时不是加1而是加权重值
3. 三维扩展：扩展到三维空间，使用三维差分或逐层二维差分