题意

有一个 n x n 的方格图，给出 m 张矩形地毯。
每张地毯用左上角 (x1, y1) 和右下角 (x2, y2) 表示，覆盖这个闭矩形里的所有格子。

要求输出每个格子被多少张地毯覆盖。

思路

先看一个最直接的朴素解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> covered(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 朴素做法：把地毯覆盖的每一个格子都加 1。
        for (int x = x1; x <= x2; ++x) {
            for (int y = y1; y <= y2; ++y) {
                ++covered[x][y];
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j > 1) cout << ' ';
            cout << covered[i][j];
        }
        cout << '\n';
    }

    return 0;
}

朴素做法对每张地毯都枚举它覆盖的所有格子。
如果 n,m <= 1000，最坏一张地毯就可能覆盖 10^6 个格子，m 张地毯会达到 10^9 级别，明显不够。

这类“矩形区域整体加一，最后一次性输出整张图”的问题，适合用二维差分。

对于一张地毯 [x1..x2][y1..y2]，我们不直接改矩形内部，而是在差分数组上改四个角：

1
2
3
4diff[x1][y1] += 1
diff[x2+1][y1] -= 1
diff[x1][y2+1] -= 1
diff[x2+1][y2+1] += 1

所有地毯都处理完以后，对 diff 做二维前缀和，就能还原每个格子的覆盖次数。

四个点的作用

这张表说明一次矩形加一时，四个差分点各自负责什么。

二维差分可以理解成二维前缀和的逆操作。
一个差分点会影响它右下方所有格子，所以要用容斥思想把矩形以外的影响切掉。
这个四点修改模型也可以参考 rbook 的 二维差分 文章。

Python 知识

• [[0] * (n + 2) for _ in range(n + 2)] 会创建互相独立的行；不能写成 [[0] * size] * size。
• 每行维护 row_sum，再加上一行同列的前缀值，可在一次双层循环中完成二维还原。
• " ".join(map(str, row)) 和外层换行 join 适合批量输出矩阵。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25import sys


input = sys.stdin.buffer.readline
n, m = map(int, input().split())
difference = [[0] * (n + 2) for _ in range(n + 2)]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    difference[x1][y1] += 1
    difference[x1][y2 + 1] -= 1
    difference[x2 + 1][y1] -= 1
    difference[x2 + 1][y2 + 1] += 1

for i in range(1, n + 1):
    row_sum = 0
    row, previous_row = difference[i], difference[i - 1]
    for j in range(1, n + 1):
        row_sum += row[j]
        row[j] = row_sum + previous_row[j]

print("\n".join(
    " ".join(map(str, row[1:n + 1]))
    for row in difference[1:n + 1]
))

复杂度

设方格大小为 n x n，地毯数量为 m。

• 每张地毯只做四次修改，处理所有地毯是 $O(m)$。
• 最后还原整张图需要扫描 n^2 个格子，是 $O(n^2)$。
• 总时间复杂度 $O(m + n^2)$。
• 空间复杂度 $O(n^2)$。

总结

这题是二维差分的直接应用。
只要题目满足“很多次矩形加法，最后统一查询每个点”的模式，就应该优先想到二维差分。
关键不是记四个式子，而是理解这四个点是在用容斥控制影响范围。