[USACO12FEB] Overplanting S

题意

求至多 $1000$ 个轴对齐矩形的覆盖并集面积，重复覆盖只计算一次。

思路

每个矩形在左边界加入一个 $y$ 区间，在右边界删除它。相邻两个事件横坐标之间，活跃矩形集合不变，因此面积增量是：

(x-\text{previous\_x})\times \text{活跃 y 区间并集长度}。

同一横坐标的事件必须成组处理。Counter 保存区间的出现次数，也能正确处理多个矩形具有相同纵向区间的情况。

示例推演

以样例数据手动走一遍：

text

1
2矩形1：左边 x=0，右边 x=4，下边 y=1，上边 y=5
矩形2：左边 x=2，右边 x=6，下边 y=2，上边 y=4

画出来：

text

1
2
3
4
5
6
7
8y=5       矩形1
     ┌──────────┐
y=4  │    ┌─────┼──────┐  矩形2从这里开始，向右伸出去
     │    │     │      │
y=2  │    └─────┼──────┘
     │          │
y=1  └──────────┘
    x=0 x=2   x=4    x=6

四条竖线把 x 轴切成 3 段：

text

1
2
3  第1段      第2段      第3段
┌───────┬───────┬───────┐
0       2       4       6

第 1 段：x=0→2，只有矩形1

尺子碰到的范围 y∈[1,5]，长度 = 4。

text

1
2
3
4
5
6
7
8
9            ┊ y=5
     ██████ ┊
     ██████ ┊ y=4
     ██████ ┊
     ██████ ┊ y=2
     ██████ ┊
     ██████ ┊ y=1
      0→2
     宽=2

面积① = 2 × 4 = 8

第 2 段：x=2→4，两个矩形都在

尺度碰到 y∈[1,5]，长度 = 4（矩形2的[2,4]包在[1,5]里面）。

text

1
2
3
4
5
6
7
8
9            ┊ y=5
     ████████┊
     ████████┊ y=4
     ████████┊
     ████████┊ y=2
     ████████┊
     ████████┊ y=1
      2→4
     宽=2

面积② = 2 × 4 = 8

第 3 段：x=4→6，只剩矩形2

尺子碰到的范围 y∈[2,4]，长度 = 2。

text

1
2
3
4
5
6
7
8
9            ┊ y=5
            ┊
            ┊ y=4
     ██████ ┊
     ██████ ┊ y=2
            ┊
            ┊ y=1
      4→6
     宽=2

面积③ = 2 × 2 = 4

加起来：8 + 8 + 4 = 20 ✅

一句话：把图沿着矩形的左右边竖着切开，每条里面"y 方向盖了多长"是固定的，面积 = 条的宽度 × 条里面盖的长度。

Python 知识

Counter[(low, high)] += change 把元组直接作为键，参见 /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md。
对 active.items() 排序后复用一维区间合并逻辑。
事件使用元组排序，自然按横坐标聚集。

替代：离散化桶算覆盖长度（“段转桶”）

这个方法可以简单记为 “段转桶”：

段：y 轴被离散化成一段一段的区间 [ys[i], ys[i+1])
桶：每段变成一个带计数器的桶，进出时 ±1
转：把"区间操作"转成"桶上计数"

covered_length 用排序 + 合并来算 y 方向覆盖长度。另一种更直白的做法：把 y 也离散化，用桶计数。

把 y 轴切成一段一段的"桶"。每个桶对应 [ys[i], ys[i+1])，只存一个数——被盖了几层。矩形进出时直接给桶 ±1，算覆盖长度时遍历所有桶，层数 > 0 的累加其真实高度。

text

1
2
3
4
5
6
7ys = [1,2,4,5]  →  3 个桶

┌─────┐     ┌─────┐     ┌─────┐
│[1,2)│     │[2,4)│     │[4,5)│
│cnt=0│     │cnt=0│     │cnt=0│
│高=1 │     │高=2 │     │高=1 │
└─────┘     └─────┘     └─────┘

矩形1 进入 y∈[1,5) → 桶 0,1,2 全部 +1：

text

1
2
3
4┌─────┐  ┌─────┐  ┌─────┐
│cnt=1│  │cnt=1│  │cnt=1│
└─────┘  └─────┘  └─────┘
覆盖长度 = 1×1 + 2×1 + 1×1 = 4 ✓

矩形2 进入 y∈[2,4) → 桶 1 +1：

text

1
2
3
4┌─────┐  ┌─────┐  ┌─────┐
│cnt=1│  │cnt=2│  │cnt=1│
└─────┘  └─────┘  └─────┘
覆盖长度 = 1 + 2 + 1 = 4 ✓  （桶1被盖2层，但高度只算一次）

矩形1 离开 → 桶 0,1,2 全部 -1：

text

1
2
3
4┌─────┐  ┌─────┐  ┌─────┐
│cnt=0│  │cnt=1│  │cnt=0│
└─────┘  └─────┘  └─────┘
覆盖长度 = 0 + 2 + 0 = 2 ✓

	排序合并	离散化桶
每次算覆盖长度	O(k log k)	O(m)
k 活跃区间数	≤1000
m 桶数		≤2000
实现	稍绕	直白

桶的做法本质就是线段树扫描线的朴素版——当 m 变大时，把 O(m) 的遍历加速到 O(log m)，就是线段树了。

代码

python

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59import sys
from collections import Counter


# ---------- 1. 读入所有矩形，生成左右竖边事件 ----------
data = iter(map(int, sys.stdin.buffer.read().split()))
events = []                     # 每个事件: (x坐标, 类型, y下界, y上界)
for _ in range(next(data)):     # 循环 N 次
    x1, y1, x2, y2 = (next(data) for _ in range(4))
    low, high = sorted((y1, y2))   # y1(上) > y2(下)，统一为 [下界, 上界]
    # 左边界 +1（进入），右边界 -1（离开）
    events += [(x1, 1, low, high), (x2, -1, low, high)]
events.sort()                   # 按 x 坐标从小到大排序
# ------------------------------------------------


# ---- 2. 计算当前活跃 y 区间的并集总长度 ----
def covered_length(active):
    """
    active : Counter{(y下界, y上界): 覆盖层数}
    返回这些区间合并后的总长度
    """
    total = 0
    right = None                # 当前合并段的右端点
    # 按左端点排序，贪心合并重叠区间
    for (left, end), count in sorted(active.items()):
        if not count:           # 层数为 0 → 实际已不活跃
            continue
        if right is None or left > right:
            total += end - left     # 新的不连续段，直接加整段
            right = end
        elif end > right:
            total += end - right    # 和当前段重叠但伸得更远，只加超出的部分
            right = end
    return total


# ---------- 3. 扫描线主循环 ----------
active = Counter()              # 当前在扫描线"内部"的 y 区间
answer = 0
previous_x = events[0][0]       # 上一个处理到的 x 坐标
i = 0

while i < len(events):
    x = events[i][0]            # 当前这一批事件的 x 坐标

    # 从 previous_x 到 x 这一条，y 方向覆盖不变
    # 面积 = 宽度 × y 方向被覆盖的总长度
    answer += (x - previous_x) * covered_length(active)

    # 处理 x 处的所有事件（可能有多个矩形同时开始/结束）
    while i < len(events) and events[i][0] == x:
        _, change, low, high = events[i]
        active[low, high] += change   # +1 进入，-1 离开
        i += 1

    previous_x = x

print(answer)

复杂度

本题规模下直接重算活跃区间并集，时间复杂度 $O(n^2\log n)$ ，空间复杂度 $O(n)$ 。

总结

扫描线把二维面积拆成若干“宽度乘覆盖高度”的竖条。

离散化 + 二维差分

另一种思路是直接对平面做 2D 差分，更贴合“格子覆盖”的直觉。

核心步骤

分别离散化所有矩形的 x 和 y 坐标，得到 xs[] 和 ys[]
2D 差分：每个矩形对离散化后的网格做差分标记
2D 前缀和：算出每个格子被覆盖的次数
累加面积：覆盖次数 > 0 的格子，面积用真实坐标差计算

格子面积记忆法

离散化把坐标轴分段，每段不一定等长。一个格子 (i,j) 对应真实世界中的一个长方形：

text

1
2
3宽度 = xs[j+1] - xs[j]
高度 = ys[i+1] - ys[i]
面积 = 宽度 × 高度

例如 xs=[0,2,4,6]，第 0 列宽 = 2-0 = 2，第 1 列宽 = 4-2 = 2，第 2 列宽 = 6-4 = 2。

ys=[1,2,4,5]，第 0 行高 = 2-1 = 1，第 1 行高 = 4-2 = 2，第 2 行高 = 5-4 = 1。

所以格子 (0,0) 面积 = 2×1 = 2，而格子 (1,1) 面积 = 2×2 = 4，不一样大。

示例跟踪（手工走一遍）

text

1
2
3
4
5矩形1: (0,5)→(4,1)  归一化 → x∈[0,4), y∈[1,5)
矩形2: (2,4)→(6,2)  归一化 → x∈[2,6), y∈[2,4)

xs = [0, 2, 4, 6]         3 列（下标 0,1,2）
ys = [1, 2, 4, 5]         3 行（下标 0,1,2）

差分数组 diff[4][4]（比行列多 1）：

diff	0	1	2	3
0	+1		-1
1		+1		-1
2		-1		+1
3	-1		+1

2D 前缀和后，被覆盖的格子及其面积：

格子(i,j)	x范围	y范围	宽×高	面积	覆盖次数
(0,0)	0→2	1→2	2×1	2	1
(0,1)	2→4	1→2	2×1	2	1
(0,2)	4→6	1→2	2×1	2	0
(1,0)	0→2	2→4	2×2	4	1
(1,1)	2→4	2→4	2×2	4	2
(1,2)	4→6	2→4	2×2	4	1
(2,0)	0→2	4→5	2×1	2	1
(2,1)	2→4	4→5	2×1	2	1
(2,2)	4→6	4→5	2×1	2	0

总面积 = 2+2+4+4+4+2+2 = 20 ✅

代码

python

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
43import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
rects = []
xs_set, ys_set = set(), set()
p = 1
for _ in range(n):
    x1, y1, x2, y2 = data[p:p+4]
    p += 4
    x_low, x_high = (x1, x2) if x1 < x2 else (x2, x1)
    y_low, y_high = (y1, y2) if y1 < y2 else (y2, y1)
    rects.append((x_low, y_low, x_high, y_high))
    xs_set.add(x_low); xs_set.add(x_high)
    ys_set.add(y_low); ys_set.add(y_high)

xs = sorted(xs_set)
ys = sorted(ys_set)

xid = {v: i for i, v in enumerate(xs)}
yid = {v: i for i, v in enumerate(ys)}

diff = [[0] * (len(xs) + 1) for _ in range(len(ys) + 1)]

for x1, y1, x2, y2 in rects:
    ix1, ix2 = xid[x1], xid[x2]
    iy1, iy2 = yid[y1], yid[y2]
    diff[iy1][ix1] += 1
    diff[iy1][ix2] -= 1
    diff[iy2][ix1] -= 1
    diff[iy2][ix2] += 1

pref = [[0] * (len(xs) + 1) for _ in range(len(ys) + 1)]
ans = 0
for i in range(len(ys)):
    si = i + 1
    for j in range(len(xs)):
        sj = j + 1
        pref[si][sj] = pref[i][sj] + pref[si][j] - pref[i][j] + diff[i][j]
        if pref[si][sj]:
            ans += (xs[j + 1] - xs[j]) * (ys[i + 1] - ys[i])

print(ans)

复杂度

离散化 O(n log n)，2D 差分 O(n)，前缀和 O(m²)，m ≤ 2000，总时间 O(n log n + m²)。