一、要解决的问题
平面上 n 个矩形（边与坐标轴平行，坐标可达 109），求它们并集的面积——重叠部分只算一次。直接离散成格子做标记，坐标范围太大存不下；扫描线把它降到 O(n log n)。
生活类比：量一堵贴满海报的墙的总覆盖面积。你不用逐格检查——拿一把直尺从左往右匀速移动，只需记录"当前直尺上被海报盖住的总长度"，再乘上直尺每次移动的距离，逐段累加就是总面积。海报的左边缘让覆盖"开始"，右边缘让覆盖"结束"。
二、核心框架
- 拆事件：每个矩形拆成两条竖边：左边缘（y₁→y₂，+1 进入事件）、右边缘（y₁→y₂，−1 离开事件）。
- 按 x 排序：所有事件按横坐标从小到大排序。
- 扫描：相邻事件 xi、xi+1 之间，"当前被覆盖的 y 总长度"不变，这段贡献 = 长度 × (xi+1 − xi)。先用旧长度算贡献，再处理事件更新。
- 维护覆盖长度：y 轴上用线段树维护"被至少一个矩形覆盖的总长度"。
三、配套技术①：离散化
y 坐标可达 109，但不同的 y 值最多 2n 个。把所有出现的 y 收集起来、排序、去重，用排名代替原值：
vector<long long> ys; // 收集所有 y₁、y₂
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
// 原值 y → 下标：lower_bound(ys.begin(), ys.end(), y) - ys.begin()关键认识：离散化后的相邻下标 i、i+1 对应一段真实长度 ys[i+1] − ys[i] 的区间。线段树的叶子不再是"一个点"，而是"一个段"——这是扫描线线段树与普通线段树最大的不同。
四、配套技术②：线段树维护覆盖（不下传）
零基础提示 · 线段树是什么：线段树把一个大区间递归对半分成一棵二叉树，每个节点负责一段区间并记录这段的汇总信息（这里是"被覆盖长度"）。修改和查询都只需访问 O(log n) 个节点。把 y 轴离散化成若干"段"后，线段树就建在这些段上。
每个线段树节点维护两个值：
cnt：该节点对应区间被完整覆盖的次数（+1 / −1 整段更新）；len：该区间内实际被覆盖的总长度。
cnt > 0 → len = 整段真实长度（ys[r+1] − ys[l]）
cnt = 0 且非叶子 → len = 左儿子 len + 右儿子 len
cnt = 0 且非叶子 → len = 左儿子 len + 右儿子 len
因为所有更新都是整段覆盖、且只查询全局总长（根节点的 len），不需要懒标记下传——这是扫描线线段树最精妙的地方：不存在的"单点查询"让它免于维护下传逻辑。
void update(int u, int l, int r, int ql, int qr, int v) { // 对[ql,qr]整体+v
if (ql <= l && r <= qr) cnt[u] += v;
else { /* 递归左右儿子（注意右边界对应段的下标换算） */ }
if (cnt[u] > 0) len[u] = ys[r+1] - ys[l];
else if (l == r) len[u] = 0;
else len[u] = len[u<<1] + len[u<<1|1];
}五、完整流程走查
| 步骤 | 动作 | 复杂度 |
|---|---|---|
| 1 | 读入 n 个矩形，拆成 2n 个事件，收集所有 y | O(n) |
| 2 | y 离散化；事件按 x 排序 | O(n log n) |
| 3 | 依次处理事件：贡献 += 根 len × (xi − xi−1)，再 update 该事件的 y 段 ±1 | O(n log n) |
| 4 | 输出累计面积 | — |
数字走查：矩形 A（x∈[0,3)，y∈[0,2)）与 B（x∈[2,5)，y∈[1,3)）
| 事件 x | 事件内容 | 本段贡献（旧覆盖长 × Δx） | 处理后覆盖段（长度） |
|---|---|---|---|
| 0 | A 进入 y[0,2) | —（起点） | [0,2)（2） |
| 2 | B 进入 y[1,3) | 2 × (2−0) = 4 | [0,3)（3） |
| 3 | A 离开 | 3 × (3−2) = 3 | [1,3)（2） |
| 5 | B 离开 | 2 × (5−3) = 4 | 无（0） |
| 合计 | 4 + 3 + 4 = 11 | ||
顺序要点：先算贡献、再处理当前事件。因为"贡献"用的是上一条线到这一条线之间的覆盖状态，属于旧长度。
六、变体：矩形周长并（P1856）
同样扫描，但线段树要额外维护：覆盖的段数、左右端点是否被覆盖。竖边贡献 = 段数 × 2 × Δx，横边贡献 = 相邻两次扫描线覆盖长度的差的绝对值。思路一致，细节更多，是面积并过关后的标准加练。
七、易错点清单
- 线段树叶子对应段 [ys[i], ys[i+1])：y 段右端点查询时排名要 −1，段数是 2n−1 而不是 2n。
- 面积、长度都要
long long：坐标 109，单个矩形面积就可达 1018。 - 事件的 y 区间是左闭右开还是闭区间，与"叶子是段"的下标换算必须自洽。
- 同 x 多条边的先后顺序对面积并无影响（整段 ±1 合并处理），但写周长并时要小心。
八、练习
- P5490【模板】扫描线（矩形面积并）
- P1856【IOI1998】矩形周长（周长并进阶）
- 真题对照：CSP-S 2024 T1 超速检测（区间选点贪心，扫描思想的简化形态）
考情提示：扫描线是 NOI 大纲 2025 修订版对提高级新增的 7 级知识点，且可与线段树、离散化组合出题，值得按"模板默写级"准备。