1. 从一道国赛题说起当“奇偶覆盖”遇上扫描线最近在复盘蓝桥杯的历年国赛真题第十一届A组的“奇偶覆盖”这道题让我印象很深。它初看像是一道普通的矩形面积并问题但多了一个“奇偶性”的约束瞬间就让问题的思考维度变得不一样了。很多朋友一看到“覆盖”和“矩形”第一反应可能就是暴力枚举或者二维差分但数据规模稍微大一点这些方法就立刻捉襟见肘了。这道题本质上是一个二维平面上的统计问题核心在于高效处理大量矩形的叠加区域并区分覆盖层数的奇偶性。这让我立刻想到了一个经典的算法组合扫描线 线段树。这个组合堪称处理一维区间覆盖、二维平面矩形问题的“屠龙刀”。扫描线负责将二维问题降维变成一系列一维的区间问题线段树则负责高效维护这些区间上的状态并进行快速的查询与更新。而“奇偶覆盖”这个条件又给线段树需要维护的信息提出了新的要求。网上能找到的很多扫描线模板都是解决面积并或周长并的直接套用来解这道题肯定会卡住。所以今天我想结合这道蓝桥杯国赛题把扫描线处理奇偶覆盖的完整思路、代码模板以及我调试时踩过的几个深坑系统地梳理一遍。无论你是正在备赛蓝桥杯还是单纯对算法竞赛中的扫描线应用感兴趣相信这篇都能给你带来一些直接的帮助。2. 问题本质拆解为什么扫描线是正解我们先抛开“奇偶”这个条件思考一个更基础的问题如何计算N个矩形在平面上的总面积即矩形面积并最直观的想法是将整个坐标平面离散化成一个个小格子然后用二维差分数组记录每个矩形对格子的贡献最后统计值大于0的格子数。这个方法在坐标范围很小比如几百时是可行的。但蓝桥杯的题目坐标值动辄$10^5$甚至$10^9$量级格子法在空间和时间上都是灾难。这时就需要扫描线算法。它的核心思想非常巧妙想象有一根垂直的线从左到右扫过整个平面。这根线在移动过程中会不断与某些矩形的左右边界相交。当扫描线位于某个位置x时我们可以求出所有与当前扫描线相交的矩形在y轴方向上的投影并集的长度len。那么扫描线从x1移动到x2的这一小段对总面积的贡献就是(x2 - x1) * len。把所有这样的小段贡献累加起来就得到了总面积。这个过程将二维的面积计算转化为了一维的区间覆盖长度统计问题。而线段树正是维护“当前被覆盖的区间总长度”的绝佳数据结构。它可以在O(log n)的时间内完成区间修改矩形的上下边加入或删除和整体查询求当前被覆盖的总长度。现在加上“奇偶覆盖”的条件。题目要求我们分别计算被覆盖次数为奇数的区域面积和被覆盖次数为偶数的区域面积。这意味着我们的线段树不能只维护“是否被覆盖”还需要维护“覆盖的层数”。更进一步我们需要知道在当前扫描线的某个y区间上覆盖层数的奇偶性是如何分布的以及对应的长度是多少。因此线段树节点需要维护的关键信息升级了cnt: 当前区间整体被覆盖的次数懒标记不下传。len_odd: 当前区间内被覆盖次数为奇数的线段总长度。len_even: 当前区间内被覆盖次数为偶数的线段总长度包括0次。这里有一个非常重要的优化思想由于我们只关心奇偶性所以覆盖次数可以模2处理。一个区间被覆盖了k次它的奇偶性只取决于k是奇数还是偶数。这大大简化了状态。3. 算法核心线段树维护奇偶覆盖长度理解了问题本质后我们来设计线段树。我们是对y坐标进行离散化后建树每个叶子节点代表一个最小的y轴区间单元如[y_i, y_{i1})。树上的每个节点对应一个y轴上的连续区间。3.1 线段树节点定义与更新策略我们定义如下的节点结构体struct Node { int l, r; // 节点代表的原始y坐标离散化后的索引范围对应区间 [ys[l], ys[r1]) int cnt; // 当前区间整体被覆盖的增量懒标记不下传 int len_odd; // 当前区间内覆盖次数为奇数的实际长度 int len_even; // 当前区间内覆盖次数为偶数的实际长度 } tr[MAXN * 4];关键点在于cnt的理解。它不是一个普通的懒标记而是一个“覆盖次数增量”。当对一个区间执行1操作表示一条矩形的上边开始覆盖cnt执行-1操作表示一条矩形的下边结束覆盖cnt--。这个cnt值记录在节点上并不下传给子节点。这是扫描线线段树与常规区间修改线段树最大的不同称为“不下传懒标记的线段树”。那么如何根据cnt和子节点的信息来更新当前节点的len_odd和len_even呢这是整个算法的核心需要分情况讨论如果当前节点cnt 0这意味着整个节点代表的区间被完全覆盖了cnt次。那么这个区间内所有点的覆盖次数都至少是cnt。因此这个区间整体的奇偶性就由cnt的奇偶性决定。如果cnt是奇数那么整个区间都属于“奇覆盖”区域len_odd就等于这个区间的实际长度 (ys[r1] - ys[l])len_even 0。如果cnt是偶数那么整个区间都属于“偶覆盖”区域len_odd 0len_even等于区间实际长度。注意此时完全不需要考虑子节点的情况因为父节点的覆盖已经“压倒”了一切。如果当前节点cnt 0这意味着当前节点代表的区间没有从祖先节点继承下来的整体覆盖。那么这个区间内每个点的覆盖次数就完全由其两个子区间的覆盖情况决定。因此当前节点的len_odd等于左儿子的len_odd加上右儿子的len_odd。同理len_even等于左儿子的len_even加上右儿子的len_even。这个更新逻辑在push_up函数中实现void push_up(int u) { if (tr[u].cnt 0) { // 整个区间被整体覆盖 int seg_len ys[tr[u].r 1] - ys[tr[u].l]; // 计算实际长度 if (tr[u].cnt % 2 1) { tr[u].len_odd seg_len; tr[u].len_even 0; } else { tr[u].len_odd 0; tr[u].len_even seg_len; } } else { // 没有整体覆盖信息由子节点合并 // 注意处理叶子节点的情况 if (tr[u].l tr[u].r) { tr[u].len_odd 0; tr[u].len_even 0; } else { tr[u].len_odd tr[u 1].len_odd tr[u 1 | 1].len_odd; tr[u].len_even tr[u 1].len_even tr[u 1 | 1].len_even; } } }注意seg_len的计算是ys[r1] - ys[l]而不是ys[r] - ys[l]。因为离散化后点ys[i]代表的是坐标线段树节点管理的是区间[ys[i], ys[i1])。这是一个非常容易出错的细节。3.2 离散化与扫描线事件处理由于坐标范围很大我们必须对y坐标进行离散化。收集所有矩形的y1和y2坐标。排序、去重得到有序的ys数组。ys[i]表示第i个离散化后的y坐标值。线段树建立时每个叶子节点i管理的是区间[ys[i], ys[i1])。所以线段树的有效节点范围是[0, ys.size() - 2]。扫描线需要处理“事件”。每个矩形产生两条垂直的线段即事件入边矩形左边界x x1对应的y区间是[y1, y2)权值1表示覆盖开始。出边矩形右边界x x2对应的y区间是[y1, y2)权值-1表示覆盖结束。我们将所有事件按x坐标排序x相同时通常先处理入边1再处理出边-1以确保边界上的点被正确计算。不过在这道题中由于我们计算的是面积区间是左闭右开的[y1, y2)先处理1还是-1影响不大但保持一个固定顺序是好习惯。事件结构体可以这样定义struct Event { int x; // 事件发生的x坐标 int y1, y2; // 影响的y区间原始坐标 int val; // 1 或 -1 bool operator(const Event other) const { if (x ! other.x) return x other.x; // 如果x相同为了保证正确性可以考虑val大的先处理即1在-1前面 // 但本题面积计算中相邻x之间无其他事件顺序可任意。为通用性我们按val降序。 return val other.val; } };处理流程的伪代码如下读取所有矩形生成事件数组events。对y坐标离散化得到ys数组。根据ys数组建立线段树通常只build设置l, rcnt和len在后续更新。将事件按x排序。初始化last_x events[0].x总面积变量area_odd 0, area_even 0。遍历排序后的事件设当前事件e的x坐标为cur_x。计算自上一个事件以来扫描线扫过的面积dx cur_x - last_x。此时线段树根节点存储的len_odd和len_even就是last_x位置时y轴上奇/偶覆盖区间的长度。area_odd dx * tr[1].len_oddarea_even dx * tr[1].len_even根据当前事件e更新线段树将e.y1和e.y2映射为离散化后的索引l和r-1因为线段树区间对应[ys[l], ys[r])而修改区间是[y1, y2)所以右端点索引要减1然后执行区间修改modify(1, l, r-1, e.val)。更新last_x cur_x。输出area_odd和area_even。4. 代码实现与模板解析下面给出基于上述思路的完整C模板。为了清晰我将关键部分拆解并加上详细注释。#include iostream #include vector #include algorithm using namespace std; const int MAXN 100010; // 根据题目矩形数量设置事件数是2N struct Event { int x, y1, y2; int val; // 1: 入边 -1: 出边 bool operator(const Event other) const { if (x ! other.x) return x other.x; // 确保同一x处先加后减避免边界问题 return val other.val; } }; vectorint ys; // 用于离散化的y坐标数组 vectorEvent events; struct Node { int l, r; int cnt; // 区间整体覆盖次数 int len_odd; // 覆盖次数为奇数的长度 int len_even; // 覆盖次数为偶数的长度 } tr[MAXN * 8]; // 线段树开4倍离散化后点数最多2N再乘4 // 离散化查找找到第一个 val 的坐标的索引 int find(int val) { return lower_bound(ys.begin(), ys.end(), val) - ys.begin(); } void push_up(int u) { if (tr[u].cnt 0) { // 整个区间被整体覆盖了 cnt 次 long long seg_len ys[tr[u].r 1] - ys[tr[u].l]; // 实际长度 if (tr[u].cnt % 2 1) { tr[u].len_odd seg_len; tr[u].len_even 0; } else { tr[u].len_odd 0; tr[u].len_even seg_len; } } else { // 没有整体覆盖信息由子节点合并 if (tr[u].l tr[u].r) { // 叶子节点且cnt0说明完全未覆盖 tr[u].len_odd 0; tr[u].len_even 0; } else { tr[u].len_odd tr[u 1].len_odd tr[u 1 | 1].len_odd; tr[u].len_even tr[u 1].len_even tr[u 1 | 1].len_even; } } } void build(int u, int l, int r) { tr[u] {l, r, 0, 0, 0}; if (l ! r) { int mid (l r) 1; build(u 1, l, mid); build(u 1 | 1, mid 1, r); // 初始时所有区间未覆盖len_odd和len_even在push_up中会设为0 } // 对于叶子节点lr区间长度为 ys[l1]-ys[l]但此时cnt0在push_up中会处理。 // 注意build时不计算长度长度在第一次push_up时根据cnt计算。 } void modify(int u, int l, int r, int val) { if (tr[u].l l tr[u].r r) { // 完全覆盖当前区间 tr[u].cnt val; push_up(u); // 覆盖次数变化立即更新当前节点的长度信息 return; } // 不需要下传cnt标记 int mid (tr[u].l tr[u].r) 1; if (l mid) modify(u 1, l, r, val); if (r mid) modify(u 1 | 1, l, r, val); push_up(u); // 用子节点更新后的信息来更新自己 } int main() { int n; cin n; for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; // 确保y1 y2, x1 x2 if (y1 y2) swap(y1, y2); if (x1 x2) swap(x1, x2); events.push_back({x1, y1, y2, 1}); // 入边 events.push_back({x2, y1, y2, -1}); // 出边 ys.push_back(y1); ys.push_back(y2); } // 1. 离散化y坐标 sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 2. 构建线段树管理区间 [0, ys.size()-2] // 因为线段树节点i代表区间 [ys[i], ys[i1])所以最大索引是 size-2 build(1, 0, ys.size() - 2); // 3. 事件排序 sort(events.begin(), events.end()); // 4. 扫描线处理 long long area_odd 0, area_even 0; int last_x events[0].x; for (const auto e : events) { int cur_x e.x; long long dx cur_x - last_x; // 计算上一段扫描线贡献的面积 area_odd dx * tr[1].len_odd; area_even dx * tr[1].len_even; // 更新线段树 int l find(e.y1); int r find(e.y2); // 注意e.y2对应的是ys[r]但区间是[y1, y2)所以修改[l, r-1] if (l r) { // 确保区间有效 modify(1, l, r - 1, e.val); } last_x cur_x; } cout area_odd endl area_even endl; return 0; }5. 关键细节与调试心得实现这个模板时有几个地方极易出错我当初调试了很久。细节一线段树区间与离散化索引的对应关系这是最大的坑。离散化数组ys存储的是坐标点。线段树叶子节点i管理的是区间[ys[i], ys[i1])。因此建树时总区间是[0, ys.size() - 2]。当你要修改一个原始区间[y1, y2)时通过find找到l find(y1),r find(y2)。ys[l]等于y1ys[r]等于y2。那么对应的线段树修改区间应该是[l, r-1]因为它代表了所有满足ys[i] y ys[i1]且i在[l, r-1]范围内的小区间。在push_up中计算节点实际长度时公式是ys[tr[u].r 1] - ys[tr[u].l]。因为tr[u].r是最后一个小区间的索引它对应的右端点是ys[tr[u].r 1]。细节二push_up逻辑的严密性必须处理好所有边界情况cnt 0时直接根据cnt的奇偶性决定整个区间的len_odd和len_even与子节点无关。cnt 0时如果是叶子节点l r说明这个最小单元区间没有任何覆盖len_odd和len_even都为0。如果不是叶子节点则len_odd和len_even分别等于左右儿子的和。 这个逻辑保证了信息传递的正确性。我曾错误地在cnt0且非叶子时直接计算区间长度作为len_even这忽略了子区间可能被单独覆盖成奇数的情况。细节三modify操作与懒标记这是扫描线线段树的精髓——cnt标记不下传。在modify函数中如果当前节点区间被完全覆盖我们只修改它的cnt然后调用push_up(u)更新它自身的len信息。然后就直接返回不继续递归到子节点也不将cnt下推。 为什么可以这样因为查询永远只查根节点的len信息。只要每个节点的len信息能根据自身的cnt和子节点的len正确计算出来那么根节点的信息就是全局正确的。cnt记录了“这个区间被整体覆盖了多少层”这个信息保存在当前节点就够了不需要让子节点也知道。push_up时如果cnt0子节点的信息被忽略如果cnt0子节点的信息才被采纳。这种设计使得每次修改的复杂度是O(log n)而不是O(n)。细节四数据范围与溢出面积可能很大x和y坐标的差值最大能到$10^5$N个矩形面积可能达到$10^{10}$量级。所以area_odd,area_even, 以及push_up中的seg_len都必须使用long long。seg_len虽然由两个int坐标相减得到但相乘后可能溢出int所以也建议用long long。调试技巧画图与小数据模拟当结果不对时最好的方法是取一个最简单的例子比如两个有重叠的小矩形手动模拟整个扫描过程。列出所有事件。列出离散化后的ys数组。画出线段树的结构标注每个节点管理的实际y区间。一步步跟踪modify操作记录每个事件处理后根节点的len_odd和len_even以及累加的面积。 这个过程能帮你迅速定位是离散化映射错了还是push_up逻辑有问题或者是面积累加的逻辑有误。6. 模板的通用性扩展这个模板解决的是“奇偶覆盖面积”问题。但它其实是一个框架通过修改线段树节点维护的信息和push_up的逻辑可以解决一系列扫描线问题矩形面积并只维护一个len覆盖长度cnt0时len等于区间长度否则len等于左右儿子len之和。push_up更简单。矩形周长并需要维护“覆盖长度”和“竖边数量”。竖边数量由区间内不连续的覆盖段数决定。这需要额外维护“区间左右端点是否被覆盖”的标志push_up时合并左右儿子信息来计算区间内的线段数。矩形覆盖k次以上的面积节点需要维护一个数组len[k]len[i]表示被覆盖至少i次的长度。push_up的逻辑会更复杂需要根据cnt和子节点的len数组进行合并计算。三维立方体体积并这就是“二维扫描线一维线段树”的推广可以尝试“三维扫描线平面扫描二维线段树面积树”但实现难度和复杂度会高很多通常需要更高级的数据结构。对于竞赛而言掌握好“面积并”和“奇偶覆盖”这两种变体已经能应对绝大多数二维平面矩形统计问题了。关键在于深刻理解“扫描线降维”的思想以及“不下传懒标记的线段树”是如何高效维护区间覆盖信息的。7. 蓝桥杯真题实战与变式思考回到“奇偶覆盖”这道题我们用上面的模板可以完美解决。输入格式通常是第一行一个整数N接下来N行每行四个整数x1 y1 x2 y2代表一个矩形。输出两行分别是奇数覆盖面积和偶数覆盖面积。这里再引申一个容易混淆的概念“偶数覆盖”包括0次覆盖吗在题目描述和通常的理解中“被覆盖次数为偶数”指的是覆盖次数大于0且为偶数。而我们的模板中len_even实际上包含了覆盖0次的情况当cnt0且为叶子节点时len_even为0但逻辑上它属于偶覆盖长度为0。这并不影响结果因为我们在计算面积时len_even始终与len_odd互补且len_odd len_even始终等于当前扫描线覆盖到的y轴总长度即ys[last] - ys[first]。题目要求的“偶数覆盖面积”其实就是总面积减去奇数覆盖面积。所以用这个模板计算出的area_even就是正确答案。最后在竞赛中遇到此类问题建议的思考步骤是判断维度是二维平面问题吗涉及矩形叠加统计吗判断算法如果坐标范围大需要离散化如果矩形数量多需要O(N log N)的算法。扫描线线段树是标准解法。设计线段树信息根据问题要求面积、周长、奇偶性、k次覆盖设计节点需要维护哪些值。设计push_up逻辑重点厘清当节点有cnt覆盖时如何计算信息当cnt为0时如何从子节点合并信息。注意边界与离散化仔细处理区间开闭、离散化索引映射、叶子节点处理等细节。把这个模板理解透彻自己动手实现一遍调试通过以后遇到类似的题目就能做到心里有数快速套用和修改了。算法竞赛中扫描线是一个重要的知识点也是一个很好的区分度题目希望这篇详细的解析能帮你拿下它。