扫描线与矩形面积并
代码模板扫描线与矩形面积并问题的原理与实现:线段树维护区间覆盖长度。
一句话算法
扫描线把矩形面积拆成一层一层的横条:线段树维护当前横向被覆盖长度,相邻两条水平边之间的高度乘这个长度就是新增面积。
问题模型
给出
直接枚举平面格子不可行,因为坐标可能很大。我们只关心矩形的上下边,因为只有扫描线经过这些边时,当前被覆盖的横向区间才会改变。

核心直觉
从下往上移动一条水平扫描线:
- 遇到矩形下边:这个矩形的横向区间开始贡献覆盖,覆盖次数
+1。 - 遇到矩形上边:这个矩形的横向区间停止贡献覆盖,覆盖次数
-1。 - 两条相邻事件边之间,横向覆盖长度不变。
于是每一层面积都是:
线段树维护的不是“区间和”,而是“当前覆盖次数大于
算法步骤
- 对每个矩形生成两条事件边:
- 下边:
[x1, x2)在高度y1加一。 - 上边:
[x1, x2)在高度y2减一。
- 下边:
- 收集所有
x1, x2做离散化。 - 线段树的每个叶子不表示一个点,而表示相邻两个离散化端点之间的一段。
- 按
y从小到大处理事件。 - 每次先用上一层横向覆盖长度乘高度差累加答案,再把当前事件更新进线段树。
- 线段树根节点始终保存当前横向被覆盖的总长度。
离散化的关键
离散化时最容易错的一点是:矩形覆盖的是区间段,不是端点。
假设离散化端点为:
x: 1 4 5 7
leaf: [1,4) [4,5) [5,7)
index: 1 2 3
所以原区间 [l,r) 对应的叶子下标是:
其中 x 在离散化端点数组中的 1-based 编号。
为什么不用 pushdown
我们只需要查询整棵树的根节点,不会向下查询某个局部区间。每次更新后只要沿递归路径重新 push_up,根节点就是正确的当前覆盖长度。
算法证明
关键不变量: 处理完高度不超过当前事件的所有边后,线段树根节点保存当前扫描线处被至少一个矩形覆盖的横向总长度。
- 叶子正确: 每个叶子表示一个真实坐标段
[x_i,x_{i+1})。如果覆盖次数大于0,整段被覆盖;否则它是否被覆盖只可能来自子段,但叶子没有子段,所以长度为0。 - 内部节点正确: 若
cover[p] > 0,说明这个节点代表的整段被某些矩形完整覆盖,长度就是右端点减左端点。若cover[p] == 0,它的覆盖长度只能来自两个儿子的并集,因此等于左右儿子覆盖长度之和。 - 事件正确: 下边让区间覆盖次数加一,上边让区间覆盖次数减一,正好模拟扫描线穿过矩形边界时的覆盖变化。
- 面积正确: 两个相邻事件高度之间没有新的边,覆盖长度不变,所以该层面积等于固定横长乘高度差。累加所有层就是并集面积。
复杂度分析
设矩形数量为
- 事件数量为
。 - 离散化和排序复杂度为
。 - 每个事件更新一次线段树,复杂度为
。 - 总时间复杂度为
。 - 空间复杂度为
。
代码实现
下面是正式竞赛模板,适用于坐标较大的矩形面积并。
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 版与 C++ 一一对应:init(segn, coords) 传入段数与 1 下标的坐标表(长度至少 segn + 2),add(ql, qr, v, 1, 1, segn) 加覆盖次数,covered_len() 读根节点的覆盖长度。递归写法与 C++ 完全同构。
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 如何决定当前覆盖长度。
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;
}
add(ql, qr, v, 1, 1, n) 与 covered_len() 与 C++ 同名同参。要求
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
两个 8,重叠部分是一个 7。
应用分类详解
扫描线的本质是:把二维覆盖问题按某个坐标排序,转成一系列一维动态覆盖问题。
一、矩形面积并
典型模式: 多个轴对齐矩形,求并集面积。
识别信号: 坐标大、矩形多、要求去重面积。
核心建模: 扫描 y,线段树维护当前被覆盖的 x 总长度。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 面积并模板 | luogu-P5490 | 离散化 x 坐标,事件边按 y 排序 |
二、矩形周长并
典型模式: 求多个矩形并集轮廓长度。 识别信号: 题目问“周长”“轮廓线”,需要统计覆盖长度变化。 核心建模: 分别扫描横向和纵向,统计覆盖长度变化量。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 周长并 | luogu-P1856 | 每条边贡献的是覆盖长度变化,而不是覆盖长度乘高度 |
三、二维离线覆盖统计
典型模式: 一维不断增删区间,另一维按事件排序。 识别信号: 操作可以按坐标排序,查询只依赖当前活跃集合。 核心建模: 扫描线维护活跃对象,线段树或树状数组回答一维信息。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 区间活跃统计 | luogu-P2163 | 一维排序,另一维用数据结构维护 |
经典例题
-
luogu-P5490 矩形面积并模板题。重点是理解叶子表示的是坐标段
[x_i,x_{i+1})。 -
luogu-P1856 矩形周长并。和面积并相比,需要维护覆盖段数、左右端点是否被覆盖等信息。
-
HDU 1542 Atlantis 浮点坐标版本的矩形面积并,离散化坐标仍然适用。