[USACO19FEB] Painting The Barn S

题意

给出 n 个坐标轴平行的矩形，每个矩形表示一次涂色区域。

矩形 (x1, y1, x2, y2) 覆盖的是半开区域 [x1,x2) * [y1,y2)，也就是所有左下角坐标满足 $x1 <= x < x2$ 且 $y1 <= y < y2$ 的单位小方格。

要求统计所有矩形涂完后，恰好被涂了 K 层的单位面积数量。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
35
36
37#include <bits/stdc++.h>
using namespace std;

const int MAXC = 1000;
int cover[MAXC + 1][MAXC + 1];

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

    int n, k;
    cin >> n >> k;

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

        // 朴素做法：直接枚举这个矩形覆盖到的每一个单位小方格。
        for (int x = x1; x < x2; x++) {
            for (int y = y1; y < y2; y++) {
                cover[x][y]++;
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < MAXC; x++) {
        for (int y = 0; y < MAXC; y++) {
            if (cover[x][y] == k) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

朴素做法对每个矩形直接枚举内部所有单位小方格。这个想法正确，但 n 最大是 100000，一个矩形又可能覆盖接近 $1000 * 1000$ 个格子，逐格修改会超时。

这题的关键模式是：很多次矩形整体加一，最后只需要统一统计结果。根据 rbook 的《差分》文章，这正适合用二维差分：每次矩形修改只改四个边界点，所有修改结束后再做一次二维前缀和还原。二维前缀和的还原方式也可以参考 rbook 的《前缀和》文章。

对一个半开矩形 [x1,x2) * [y1,y2)，差分数组这样修改：

text

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

注意这里不是 x2 + 1、y2 + 1。题目里的右上角本来就不属于涂色区域，所以 x2 和 y2 正好是影响停止的位置。

四个点的作用

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

差分点	操作	含义
`(x1, y1)`	`+1`	从矩形左下角开始，让右上方向的格子多一层
`(x2, y1)`	`-1`	从右边界开始，取消继续向右的影响
`(x1, y2)`	`-1`	从上边界开始，取消继续向上的影响
`(x2, y2)`	`+1`	右上区域被取消了两次，需要补回来

最后从小到大扫描 diff，用二维前缀和公式原地还原覆盖次数。若当前点 (x,y) 是一个真实单位格子的左下角，也就是 x < 1000 且 y < 1000，就判断它的覆盖次数是否等于 K。

代码

cpp

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
35
36
37
38
39
40
41
42#include <bits/stdc++.h>
using namespace std;

const int MAXC = 1000;
int diffv[MAXC + 2][MAXC + 2];

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

    int n, k;
    cin >> n >> k;

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

        // 题目给出的矩形是 [x1, x2) * [y1, y2)，右上边界本身不被涂色。
        // 因此二维差分的停止位置就是 x2 和 y2。
        diffv[x1][y1]++;
        diffv[x2][y1]--;
        diffv[x1][y2]--;
        diffv[x2][y2]++;
    }

    int ans = 0;
    for (int x = 0; x <= MAXC; x++) {
        for (int y = 0; y <= MAXC; y++) {
            if (x > 0) diffv[x][y] += diffv[x - 1][y];
            if (y > 0) diffv[x][y] += diffv[x][y - 1];
            if (x > 0 && y > 0) diffv[x][y] -= diffv[x - 1][y - 1];

            // 只有左下角为 (0..999, 0..999) 的单位小方格有面积。
            if (x < MAXC && y < MAXC && diffv[x][y] == k) {
                ans++;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设坐标上界为 $C = 1000$ 。

每个矩形只做四次差分修改，处理所有矩形是 $O(n)$ 。
还原并统计整个网格是 $O(C^2)$ 。
总时间复杂度 $O(n + C^2)$ 。
空间复杂度 $O(C^2)$ 。

总结

这题和普通二维差分模板最大的细节区别，是矩形坐标表示半开区域。

只要确认了覆盖的是 [x1,x2) * [y1,y2)，四个差分点就自然落在 (x1,y1)、(x2,y1)、(x1,y2)、(x2,y2)。最后扫描时也要只统计 $0 \dots 999$ 的单位格子，不能把坐标边界 1000 当成面积。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。