cp-algorithms：线段并集长度计算——Klee 算法的 O(n log n) 解法

给定数轴上的 n 条线段（每条线段由一对端点坐标 (a_i1, a_i2) 描述），求它们并集的总长度，是计算几何与算法竞赛中的经典入门问题。本文基于 cp-algorithms 仓库中 长度并集文档，详细讲解由 Klee 于 1977 年提出的扫描式算法：先对全部端点排序，再通过维护"当前已打开线段计数"的单一扫描即可得到答案，时间复杂度 O(n log n) 且已被证明渐进最优。读完本文，你将掌握该算法的原理、完整可运行的 C++ 实现、正确性论证，以及它在浮点坐标、闭区间等变体下的适配方法。

问题定义

给定 n 条线段，每条线段由一对坐标 $(a_{i1}, a_{i2})$ 描述。线段位于同一条数轴上（一维情形），因此每一条线段就是一个闭区间 $[a_{i1}, a_{i2}]$（不妨设 $a_{i1} \le a_{i2}$）。

我们要求的是这些线段并集的长度，即所有线段覆盖过的总长度。如果若干条线段相互重叠，重叠部分只计算一次。形式化地说，并集长度等于覆盖次数大于 0 的所有区间长度之和：

$$\text{len} = \int_{-\infty}^{+\infty} [\text{区间 } x \text{ 被至少一条线段覆盖}] \, dx$$

朴素思路及其代价

最直接的做法是：先把所有线段按左端点排序，再顺序合并区间——对相邻两个区间，如果当前区间的右端点不小于下一个区间的左端点，就把它们合并为一个新区间，否则累加当前合并结果的长度。虽然排序版本的合并思路也能做到 O(n log n)，但需要额外处理合并逻辑和边界细节。

另一种更朴素的思路是直接两两判断重叠并按"并集去重"，复杂度可达 O(n²)，且去重过程繁琐易错。Klee 算法提供了一种更优雅、代码更短的统一扫描框架。

Klee 算法：核心思想

Klee 在 1977 年提出的算法基于一个非常简洁的观察：

若把 n 条线段的全部 2n 个端点混在一起按坐标排序，然后从左到右扫描，并维护一个计数器 c 表示"当前时刻已被打开（尚未结束）的线段条数"，那么任意相邻两个端点 $x_{i-1}$ 与 $x_i$ 之间的区间，当且仅当 $c > 0$（至少有 1 条线段处于打开状态）时，才属于并集的一部分，其贡献长度为 $x_i - x_{i-1}$。

算法的操作步骤：

1. 将每条线段的左、右两个端点放入数组 x 中，同时记录每个端点的类型（左端点或右端点）。
2. 将 x 按坐标值排序；当坐标相同时，数组中的先后顺序不影响结果（见下文正确性分析）。
3. 从左到右遍历排序后的端点数组，维护计数器 c：
   • 遇到左端点：c++，表示一条线段开始覆盖；
   • 遇到右端点：c--，表示一条线段覆盖结束。
4. 在移动到下一个端点坐标之前，若 $i > 0$ 且 $c > 0$，则把 $x_i - x_{i-1}$ 累加到结果中。

由于扫描方向始终是数轴正方向，所有被至少一条线段覆盖的相邻端点间隙都会被计入且只计入一次，重叠部分自然不会被重复计算。

实现与逐行解读

仓库文档 length-of-segments-union.md 给出了完整的 C++ 实现，这里做逐行拆解：

int length_union(const vector<pair<int, int>> &a) {
    int n = a.size();
    vector<pair<int, bool>> x(n*2);
    for (int i = 0; i < n; i++) {
        x[i*2] = {a[i].first, false};
        x[i*2+1] = {a[i].second, true};
    }

    sort(x.begin(), x.end());

    int result = 0;
    int c = 0;
    for (int i = 0; i < n * 2; i++) {
        if (i > 0 && x[i].first > x[i-1].first && c > 0)
            result += x[i].first - x[i-1].first;
        if (x[i].second)
            c--;
        else
            c++;
    }
    return result;
}

要点说明：

• 数据结构：x[i] 是一个 pair<int, bool>，first 是端点坐标，second 标记端点类型。在原文约定中，false 表示左端点、true 表示右端点。数组大小恰为 2n，因为每条线段贡献两个端点。
• 排序：对 pair 排序时，C++ 默认先按 first（坐标）比较，再按 second（类型标记，false < true）比较。也就是说，同一坐标处左端点会排在右端点之前。这一点保证了正确性：当多个端点重合时，所有左端点先被处理（先 c++），随后右端点再被处理（后 c--），从而同一坐标处"先开后关"，不会因某条线段在本坐标结束而导致瞬时计数被错误压低。
• 长度累加：x[i].first > x[i-1].first 保证只有在坐标确实发生变化时才累加；若相邻端点坐标相同，差值为 0，累加与否都不影响结果。c > 0 则是"当前区间确实被覆盖"的充要条件。
• 计数更新：处理完当前端点后立即更新 c。顺序上"先累加再更新"意味着：以左端点开头的区间，其首个间隙从该左端点起就算作覆盖；而以右端点收尾的区间，其尾部间隙到该右端点为止，之后 c 减一，不再计入。

一个完整示例

设有 3 条线段：[1, 4]、[2, 6]、[7, 9]。

端点	1 (L)	2 (L)	4 (R)	6 (R)	7 (L)	9 (R)
处理前 c	0	1	2	1	0	1
间隙贡献	—	1→2 计 1	2→4 计 2	4→6 计 2	—	7→9 计 2

并集总长度 = 1 + 2 + 2 + 2 = 7。直观验证：[1,6] 并 [7,9]，总长 5 + 2 = 7，正确。

正确性论证

算法的正确性可以归结为三点：

1. 覆盖间隙与开放计数的一一对应：在任意相邻端点 $x_{i-1}$ 与 $x_i$ 之间，没有新的端点出现，因此每条线段的覆盖状态在该开区间内保持不变。该区间被覆盖，当且仅当"当前被打开的线段数 c > 0"。
2. 无重复计数：排序后的端点把数轴切分成若干互不相交的开区间，扫描过程对每个间隙至多累加一次，重叠部分不会重复计算。
3. 端点重合的边界处理：同一坐标处可能出现多个端点的混合（如一条线段的右端点与另一条线段的左端点重合）。由于 pair 排序将左端点排在右端点之前，先 c++ 再 c-- 的顺序保证在重合坐标处计数不会瞬间降到 0，从而相邻间隙的长度累加不受端点重合影响。

复杂度与渐进最优性

• 排序：对 2n 个端点排序，O(n log n)；
• 扫描：单趟遍历 2n 个端点，每个端点 O(1) 操作，合计 O(n)；
• 总复杂度：O(n log n)，空间 O(n)（存储 2n 个端点）。

值得强调的是，文档明确指出该复杂度已被证明是渐进最优的：任何求线段并集长度的算法都必须读取全部输入端点（至少 Ω(n)），而对一般输入做比较型判定时需要排序信息，下界为 Ω(n log n)。因此 Klee 算法在渐进意义下不可能被进一步改进。

工程与实战细节

数据类型与坐标范围

原实现的 a 是 vector<pair<int, int>>，适用于整数坐标。若题目给出浮点坐标，只需将 int 替换为 double，并注意比较 x[i].first > x[i-1].first 时改用容差判断（如 > EPS），防止浮点精度导致间隙被误加：

const double EPS = 1E-9;
// ...
if (i > 0 && x[i].first - x[i-1].first > EPS && c > 0)
    result += x[i].first - x[i-1].first;

若坐标范围较大（如达到 10⁹ 且线段条数很多），结果变量应使用 long long 以避免整数溢出。

与"合并区间"思路的对比

另一条常见路线是：将所有线段按左端点排序，再顺序合并重叠区间，合并完成后再累加长度。该路线同样为 O(n log n)。两种方法各有取舍：

• 合并区间法：需要维护当前合并段的左右端点，逻辑稍多，但天然输出"哪些连续区间构成并集"，方便后续做区间查询类扩展；
• Klee 扫描法：只需一个计数器，代码最短，且与"求覆盖点计数 >= k 的长度"这类变体天然兼容（把 c > 0 改为 c >= k 即可），是更通用的框架。

变体：求覆盖 k 次以上的总长度

Klee 计数器的精髓在于它是"覆盖次数"的实时记录。因此求"被至少 k 条线段覆盖的总长度"只需把累加条件从 c > 0 改为 c >= k。这一思想在竞赛中常与差分数组结合使用。

在仓库中的定位与配套测试

该文档位于仓库的 geometry 目录，并已注册进全站导航文件 navigation.md（条目为 "Length of the union of segments"），属于 Geometry 分类下 "Elementary operations" 小节，与其并列的是线段求交系列：线段方程、直线交点、判断两线段相交、线段求交 等，构成完整的线段几何基础。

从仓库结构看，本项目对每个算法文档都建立了自动测试流水线：

• test/extract_snippets.py 会遍历 src/ 下所有 Markdown 文档，提取文档中标注 {.cpp file=...} 的代码块，生成对应的 .h 头文件；
• test/test.sh 随后用 g++ -std=c++17 -fsanitize=undefined -fno-sanitize-recover 编译每个测试文件并运行断言。

这意味着仓库内每个算法的示例代码都会被真实编译与执行验证。若需要为本算法补充单元测试，可将实现提取为头文件后，在 test 目录仿照其他 test_*.cpp 的写法编写断言并运行 test/test.sh 进行验证。此外，仓库 README（README.md）表明项目源自对 e-maxx.ru 算法资源（含"线段并集长度"原文）的翻译与扩展，本文档标注的 e_maxx_link: length_of_segments_union 即指向原始出处，供读者对照参考。

延伸阅读

线段并集长度是一维扫描思想的起点，仓库中与之承接的进阶内容包括：

• 扫描线求平面内线段交点：将一维端点扫描推广到二维扫描线，用平衡树维护与扫描线相交的线段顺序，同样达到 O(n log n)；
• 判断两线段是否相交：线段几何最基础的相交判定，可用于线段并集之外的交点类问题；
• 线段求交实现：给出带 EPS 容差、支持浮点与退化情形的完整求交实现。

掌握 Klee 算法，你就掌握了一维区间覆盖问题的标准解法：排序端点 + 开放计数，这一模式在扫描线、区间合并、多重覆盖统计等问题中反复出现，是通往更复杂几何算法（如平面扫描线、区间并、矩形并面积）的第一级台阶。