扫描线与矩形面积并

代码模板

扫描线与矩形面积并问题的原理与实现:线段树维护区间覆盖长度。

一句话算法

扫描线把矩形面积拆成一层一层的横条:线段树维护当前横向被覆盖长度,相邻两条水平边之间的高度乘这个长度就是新增面积。

问题模型

给出 nn 个轴对齐矩形,每个矩形由左下角 (x1,y1)(x_1,y_1) 和右上角 (x2,y2)(x_2,y_2) 描述,要求所有矩形的并集面积。

直接枚举平面格子不可行,因为坐标可能很大。我们只关心矩形的上下边,因为只有扫描线经过这些边时,当前被覆盖的横向区间才会改变。

核心直觉

从下往上移动一条水平扫描线:

  • 遇到矩形下边:这个矩形的横向区间开始贡献覆盖,覆盖次数 +1。
  • 遇到矩形上边:这个矩形的横向区间停止贡献覆盖,覆盖次数 -1。
  • 两条相邻事件边之间,横向覆盖长度不变。

于是每一层面积都是:

当前覆盖横长×下一条边的高度差 \text{当前覆盖横长} \times \text{下一条边的高度差}

线段树维护的不是“区间和”,而是“当前覆盖次数大于 00 的总长度”。

算法步骤

  1. 对每个矩形生成两条事件边:
    • 下边:[x1, x2) 在高度 y1 加一。
    • 上边:[x1, x2) 在高度 y2 减一。
  2. 收集所有 x1, x2 做离散化。
  3. 线段树的每个叶子不表示一个点,而表示相邻两个离散化端点之间的一段。
  4. 按 y 从小到大处理事件。
  5. 每次先用上一层横向覆盖长度乘高度差累加答案,再把当前事件更新进线段树。
  6. 线段树根节点始终保存当前横向被覆盖的总长度。

离散化的关键

离散化时最容易错的一点是:矩形覆盖的是区间段,不是端点。

假设离散化端点为:

x:       1      4      5      7
leaf:    [1,4)  [4,5)  [5,7)
index:      1      2      3

所以原区间 [l,r) 对应的叶子下标是:

d(l),d(r)−1 d(l), d(r)-1

其中 d(x)d(x) 表示坐标 x 在离散化端点数组中的 1-based 编号。

为什么不用 pushdown

我们只需要查询整棵树的根节点,不会向下查询某个局部区间。每次更新后只要沿递归路径重新 push_up,根节点就是正确的当前覆盖长度。

算法证明

关键不变量: 处理完高度不超过当前事件的所有边后,线段树根节点保存当前扫描线处被至少一个矩形覆盖的横向总长度。

  1. 叶子正确: 每个叶子表示一个真实坐标段 [x_i,x_{i+1})。如果覆盖次数大于 0,整段被覆盖;否则它是否被覆盖只可能来自子段,但叶子没有子段,所以长度为 0。
  2. 内部节点正确: 若 cover[p] > 0,说明这个节点代表的整段被某些矩形完整覆盖,长度就是右端点减左端点。若 cover[p] == 0,它的覆盖长度只能来自两个儿子的并集,因此等于左右儿子覆盖长度之和。
  3. 事件正确: 下边让区间覆盖次数加一,上边让区间覆盖次数减一,正好模拟扫描线穿过矩形边界时的覆盖变化。
  4. 面积正确: 两个相邻事件高度之间没有新的边,覆盖长度不变,所以该层面积等于固定横长乘高度差。累加所有层就是并集面积。

复杂度分析

设矩形数量为 nn。

  • 事件数量为 2n2n。
  • 离散化和排序复杂度为 O(nlog⁡n)O(n\log n)。
  • 每个事件更新一次线段树,复杂度为 O(log⁡n)O(\log n)。
  • 总时间复杂度为 O(nlog⁡n)O(n\log n)。
  • 空间复杂度为 O(n)O(n)。

代码实现

下面是正式竞赛模板,适用于坐标较大的矩形面积并。

C++
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h> using namespace std; using ll = long long; // 扫描线线段树(离散化版):坐标很大时先把 x 坐标压成 1..n 的段号。 // 与朴素版一样,cover 只挂在整段被覆盖的节点上,不需要懒标记下传。 const int maxn = 100000 + 5; // 坐标段数上限,按题目规模调整 int cover[maxn << 2]; // cover[p]:节点 p 管辖区间被完整覆盖的次数 ll len[maxn << 2]; // len[p]:节点 p 管辖区间内被覆盖的实际长度 int xs[maxn]; // xs[1..n+1]:离散化后的 x 坐标,第 i 段是 [xs[i], xs[i+1]) int ls(int p) { return p << 1; } // p 的左儿子 2p int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1 // 上推:自己的 cover > 0 说明整段被覆盖,长度按坐标差算; // 否则由两个孩子拼起来。叶子且 cover == 0 时长度是 0。 void pushup(int p, int l, int r) { if (cover[p] > 0) len[p] = xs[r + 1] - xs[l]; else if (l == r) len[p] = 0; else len[p] = len[ls(p)] + len[rs(p)]; } // 区间加覆盖次数:给第 [ql, qr] 段增加 v(v = +1 表示入边,-1 表示出边) void add(int ql, int qr, int v, int p, int l, int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { cover[p] += v; pushup(p, l, r); return; } int mid = (l + r) >> 1; add(ql, qr, v, ls(p), l, mid); add(ql, qr, v, rs(p), mid + 1, r); pushup(p, l, r); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; struct Event { int x1, x2, y, delta; }; vector<Event> events; events.reserve(2 * n); vector<int> xv; xv.reserve(2 * n); for (int i = 0; i < n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; events.push_back({x1, x2, y1, 1}); events.push_back({x1, x2, y2, -1}); xv.push_back(x1); xv.push_back(x2); } sort(events.begin(), events.end(), [](const Event &a, const Event &b) { return a.y < b.y; }); // 离散化:把 x 坐标压成连续的段号 sort(xv.begin(), xv.end()); xv.erase(unique(xv.begin(), xv.end()), xv.end()); int cnt = (int)xv.size(); for (int i = 0; i < cnt; i++) xs[i + 1] = xv[i]; int segn = cnt - 1; // 一共 segn 段:[xs[i], xs[i+1]) if (segn <= 0) { cout << 0 << '\n'; return 0; } ll ans = 0; int last_y = events[0].y; ll last_len = 0; for (const Event &e : events) { ans += last_len * (e.y - last_y); // 左闭右开:覆盖 [x1, x2) 就是第 [rank(x1), rank(x2)-1] 段 int l = lower_bound(xv.begin(), xv.end(), e.x1) - xv.begin() + 1; int r = lower_bound(xv.begin(), xv.end(), e.x2) - xv.begin(); if (l <= r) add(l, r, e.delta, 1, 1, segn); last_len = len[1]; last_y = e.y; } cout << ans << '\n'; return 0; }
Python

Python 版与 C++ 一一对应:init(segn, coords) 传入段数与 1 下标的坐标表(长度至少 segn + 2),add(ql, qr, v, 1, 1, segn) 加覆盖次数,covered_len() 读根节点的覆盖长度。递归写法与 C++ 完全同构。

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
# 扫描线线段树:维护区间被完整覆盖的次数与覆盖长度。 # 这个结构不需要懒标记下传:cover 只挂在整段被覆盖的节点上, # 每个节点的覆盖长度由自己的 cover 和孩子信息当场算出。 # 与 C++ 版一一对应:全局列表 cover / len + init(n) + 独立函数。 # 第 i 段是 [xs[i], xs[i+1]),段号 1..n,所以 xs 要开到 n+2。 cover: list[int] = [] # cover[p]:节点 p 管辖区间被完整覆盖的次数 len_: list[int] = [] # len_[p]:节点 p 管辖区间内被覆盖的实际长度 xs: list[int] = [] # xs[1..n+1]:离散化后的坐标 n: int = 0 # 坐标段数 def init(size: int, coords: list[int]) -> None: """重置为 size 段、坐标表 coords(1 下标,长度至少 size + 2)。""" global n, cover, len_, xs n = size cover = [0] * (n * 4 + 5) len_ = [0] * (n * 4 + 5) xs = coords def ls(p: int) -> int: return p << 1 # 左儿子 2p def rs(p: int) -> int: return p << 1 | 1 # 右儿子 2p+1 def pushup(p: int, l: int, r: int) -> None: """上推:cover > 0 说明整段被覆盖,长度按坐标差算;否则由两个孩子拼起来。""" if cover[p] > 0: len_[p] = xs[r + 1] - xs[l] elif l == r: len_[p] = 0 # 叶子且没被完整覆盖,长度为 0 else: len_[p] = len_[ls(p)] + len_[rs(p)] def add(ql: int, qr: int, v: int, p: int, l: int, r: int) -> None: """给第 [ql, qr] 段增加覆盖次数 v(+1 入边,-1 出边)。""" if qr < l or r < ql: return if ql <= l and r <= qr: cover[p] += v pushup(p, l, r) return mid = (l + r) >> 1 add(ql, qr, v, ls(p), l, mid) add(ql, qr, v, rs(p), mid + 1, r) pushup(p, l, r) def covered_len() -> int: """整棵树(根节点)的覆盖长度,即当前这一层被覆盖的总长度。""" return len_[1]

无离散化版本只适合坐标范围很小的入门理解,用来观察 cover 如何决定当前覆盖长度。

C++
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h> using namespace std; using ll = long long; // 扫描线线段树:维护区间被完整覆盖的次数与覆盖长度。 // 这个结构不需要懒标记下传:cover 只挂在整段被覆盖的节点上, // 每个节点的覆盖长度由自己的 cover 和孩子信息当场算出。 const int maxn = 100000 + 5; // 坐标段数上限,按题目规模调整 int cover[maxn << 2]; // cover[p]:节点 p 管辖区间被完整覆盖的次数 int len[maxn << 2]; // len[p]:节点 p 管辖区间内被覆盖的长度 int ls(int p) { return p << 1; } // p 的左儿子 2p int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1 // 上推:自己的 cover > 0 说明整段被覆盖;否则由两个孩子拼起来 // 叶子且 cover == 0 时长度是 0,必须单独处理,否则会去读不存在孩子 void pushup(int p, int l, int r) { if (cover[p] > 0) len[p] = r - l + 1; else if (l == r) len[p] = 0; else len[p] = len[ls(p)] + len[rs(p)]; } // 区间加覆盖次数:给 [ql, qr] 增加 v(v = +1 表示入边,-1 表示出边) void add(int ql, int qr, int v, int p, int l, int r) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { cover[p] += v; pushup(p, l, r); return; } int mid = (l + r) >> 1; add(ql, qr, v, ls(p), l, mid); add(ql, qr, v, rs(p), mid + 1, r); pushup(p, l, r); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // 每个矩形拆成入边和出边两个事件,按 y 排序后从上往下扫 struct Event { int x1, x2, y, delta; }; vector<Event> events; events.reserve(2 * n); int max_x = 0; for (int i = 0; i < n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; events.push_back({x1, x2 - 1, y1, 1}); events.push_back({x1, x2 - 1, y2, -1}); max_x = max(max_x, x2 - 1); } sort(events.begin(), events.end(), [](const Event &a, const Event &b) { return a.y < b.y; }); int xn = max_x + 2; ll ans = 0; int last_y = events.empty() ? 0 : events[0].y; int last_len = 0; for (const Event &e : events) { ans += 1LL * last_len * (e.y - last_y); // 上一层的高度先结账 if (e.x1 <= e.x2) add(e.x1, e.x2, e.delta, 1, 1, xn); last_len = len[1]; // 根节点的覆盖长度就是当前这一层的高度 last_y = e.y; } cout << ans << '\n'; return 0; }
Python

add(ql, qr, v, 1, 1, n) 与 covered_len() 与 C++ 同名同参。要求 x∈[1,max⁡_x]x \in [1, \max\_x] 且 x1⩽x2x_1 \leqslant x_2:越界坐标会让区间 l>rl > r 递归失控(C++ 同样如此,模板不防御)。

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
# 扫描线线段树(朴素版):坐标范围不大时直接按坐标建树,不做离散化。 # 这个结构不需要懒标记下传:cover 只挂在整段被覆盖的节点上, # 每个节点的覆盖长度由自己的 cover 和孩子信息当场算出。 # 与 C++ 版一一对应:全局列表 cover / len + init(n) + 独立函数。 cover: list[int] = [] # cover[p]:节点 p 管辖区间被完整覆盖的次数 len_: list[int] = [] # len_[p]:节点 p 管辖区间内被覆盖的长度 n: int = 0 # 坐标段数 def init(size: int) -> None: """重置为坐标段数 size;换一组数据前必须先调用。""" global n, cover, len_ n = size cover = [0] * (n * 4 + 5) len_ = [0] * (n * 4 + 5) def ls(p: int) -> int: return p << 1 # 左儿子 2p def rs(p: int) -> int: return p << 1 | 1 # 右儿子 2p+1 def pushup(p: int, l: int, r: int) -> None: """上推:cover > 0 说明整段被覆盖;否则由两个孩子拼起来。""" if cover[p] > 0: len_[p] = r - l + 1 elif l == r: len_[p] = 0 # 叶子且没被完整覆盖,长度为 0 else: len_[p] = len_[ls(p)] + len_[rs(p)] def add(ql: int, qr: int, v: int, p: int, l: int, r: int) -> None: """给 [ql, qr] 增加覆盖次数 v(+1 入边,-1 出边)。""" if qr < l or r < ql: return if ql <= l and r <= qr: cover[p] += v pushup(p, l, r) return mid = (l + r) >> 1 add(ql, qr, v, ls(p), l, mid) add(ql, qr, v, rs(p), mid + 1, r) pushup(p, l, r) def covered_len() -> int: """整棵树(根节点)的覆盖长度,即当前这一层被覆盖的总长度。""" return len_[1]

测试用例

输入:

2
1 1 3 3
2 2 4 4

输出:

7

两个 2×22 \times 2 的矩形面积和为 8,重叠部分是一个 1×11 \times 1 的正方形,所以并集面积为 7。

应用分类详解

扫描线的本质是:把二维覆盖问题按某个坐标排序,转成一系列一维动态覆盖问题。

一、矩形面积并

典型模式: 多个轴对齐矩形,求并集面积。 识别信号: 坐标大、矩形多、要求去重面积。 核心建模: 扫描 y,线段树维护当前被覆盖的 x 总长度。

应用场景 经典题目 核心思路
面积并模板 luogu-P5490 离散化 x 坐标,事件边按 y 排序

二、矩形周长并

典型模式: 求多个矩形并集轮廓长度。 识别信号: 题目问“周长”“轮廓线”,需要统计覆盖长度变化。 核心建模: 分别扫描横向和纵向,统计覆盖长度变化量。

应用场景 经典题目 核心思路
周长并 luogu-P1856 每条边贡献的是覆盖长度变化,而不是覆盖长度乘高度

三、二维离线覆盖统计

典型模式: 一维不断增删区间,另一维按事件排序。 识别信号: 操作可以按坐标排序,查询只依赖当前活跃集合。 核心建模: 扫描线维护活跃对象,线段树或树状数组回答一维信息。

应用场景 经典题目 核心思路
区间活跃统计 luogu-P2163 一维排序,另一维用数据结构维护

经典例题

  1. luogu-P5490 矩形面积并模板题。重点是理解叶子表示的是坐标段 [x_i,x_{i+1})。

  2. luogu-P1856 矩形周长并。和面积并相比,需要维护覆盖段数、左右端点是否被覆盖等信息。

  3. HDU 1542 Atlantis 浮点坐标版本的矩形面积并,离散化坐标仍然适用。

参考