1. 问题引入从“覆盖”到“奇偶覆盖”的思维跃迁在算法竞赛和实际开发中处理二维平面上的矩形覆盖问题是一个经典课题。比如我们常遇到的问题是给定若干个矩形求它们覆盖区域的总面积。解决这类问题的利器是“扫描线算法”它通过将二维问题降维到一维来处理效率很高。然而蓝桥杯国赛这道“奇偶覆盖”题目在经典面积覆盖问题上增加了一个“奇偶性”的约束瞬间将问题的难度和思考维度提升了一个档次。它不再满足于“有没有覆盖”而是开始关心“覆盖了多少层”。我第一次看到这个题目时第一反应也是扫描线。但仔细一想经典扫描线求的是覆盖区域的并集面积它只关心某个位置是否被至少一个矩形覆盖即覆盖层数1。而“奇偶覆盖”要求我们分别统计被覆盖了奇数次的区域面积和偶数次的区域面积。这意味着我们需要维护的信息从简单的“是否被覆盖”的布尔状态变成了一个需要动态维护的“覆盖层数”的整数状态。这个转变正是这道题的核心挑战和魅力所在。它迫使我们去重新审视扫描线算法的数据结构内核思考如何高效地维护区间上的覆盖计数并从中分离出奇偶信息。简单来说题目可以抽象为在平面上有 N 个矩形每个矩形给出其左下角(x1, y1)和右上角(x2, y2)坐标。我们需要计算所有矩形覆盖完成后平面上被覆盖了奇数次的点的总面积记为S_odd和被覆盖了偶数次的点的总面积记为S_even。注意没有被任何矩形覆盖的点其覆盖次数为0属于偶数次覆盖。因此整个平面面积通常是一个足够大的、包含所有矩形的范围等于S_odd S_even。2. 核心思路剖析扫描线框架下的信息升级要解决这个问题我们必须沿用扫描线算法的基本框架但对其内部维护的数据结构进行“升级改造”。2.1 经典扫描线算法回顾首先我们快速回顾一下用于求矩形面积并的经典扫描线算法离散化将所有矩形的垂直边x坐标收集起来排序去重。这样就将连续的x轴划分成了若干个离散的区间。矩形的水平边y坐标也需要离散化用于确定扫描的上下界但核心的线段树是建立在离散化后的x区间上的。事件处理将每个矩形拆分成两个“事件”入边矩形下边yy1和出边矩形上边yy2。每个事件包含其y坐标、对应的x区间[x1, x2)以及一个权重flag入边为1表示增加一层覆盖出边为-1表示减少一层覆盖。扫描过程将所有事件按y坐标从小到大排序。然后从上到下或从下到上进行扫描。线段树维护使用线段树维护在当前扫描线y坐标上x轴方向每个区间被覆盖的情况。线段树的每个节点通常维护两个信息cnt当前区间被完整覆盖的次数懒标记思想不下传。len当前区间内被覆盖的长度即cnt 0的区间的总长度。面积累加当从一条扫描线y_prev移动到下一条扫描线y_cur时中间的高度差为dy y_cur - y_prev。此时线段树根节点维护的len就是当前x轴上被覆盖的总长度。那么这部分矩形面积就是len * dy。将其累加到总面积中。这个算法的精妙之处在于线段树的cnt标记不下传我们只关心cnt是否大于0。len的更新逻辑是如果当前节点cnt 0则len等于该节点所代表区间的实际长度。否则cnt 0len等于其左右子节点len之和对于叶子节点len0。2.2 奇偶覆盖的信息维护挑战对于奇偶覆盖我们不能只关心cnt是否大于0而必须知道cnt的确切值至少要知道它的奇偶性。然而如果直接维护每个区间确切的cnt在合并区间信息时会非常困难因为一个区间的覆盖层数可能是不均匀的。这里的关键洞察是我们并不需要知道每个点确切的覆盖次数只需要知道整个区间内覆盖次数为奇数和偶数的总长度分别是多少。而覆盖次数的奇偶性只与cnt的奇偶性有关。因此我们可以对线段树的每个节点维护一个更丰富的信息集合。设线段树节点对应区间[l, r)离散化后的区间索引。我们为每个节点维护一个数组len[2]其中len[0]在该节点对应的x轴区间内覆盖次数为偶数的点的总长度。len[1]在该节点对应的x轴区间内覆盖次数为奇数的点的总长度。同时节点依然需要维护懒标记cnt表示这个区间被整体“增加”的覆盖层数入边1出边-1。那么核心问题转化为如何根据子节点的len[0/1]和本节点的懒标记cnt来更新本节点的len[0/1]2.3 区间信息合并与懒标记应用逻辑这是本题最核心的推导部分。我们分情况讨论节点信息的更新push_up和懒标记的应用apply。1. 叶子节点如果节点是叶子节点即l1 r代表一个最小的不可再分的x轴单元区间那么这个区间的长度是固定的记为interval_len通过离散化数组计算得出。如果该节点的cnt是偶数包括0那么这个区间全部被覆盖了偶数次。所以len[0] interval_len,len[1] 0。如果该节点的cnt是奇数那么这个区间全部被覆盖了奇数次。所以len[0] 0,len[1] interval_len。2. 非叶子节点对于非叶子节点它的信息需要由其左右孩子合并而来。但这里有一个关键在合并之前必须考虑当前节点自身的懒标记cnt对左右孩子信息的影响。 因为懒标记cnt表示“这个区间被整体多覆盖了cnt层”。左右孩子统计的len[0/1]是在它们各自当前覆盖层数基础上的奇偶长度。而当前节点的len[0/1]需要反映的是在叠加了当前节点的cnt之后整个区间的奇偶覆盖长度。设当前节点为u其左右孩子为lc和rc。u.cnt是当前节点的懒标记。lc.len[0/1]和rc.len[0/1]是左右孩子在它们自身懒标记影响下的奇偶长度。那么对于节点u从lc贡献的长度中原本覆盖次数为偶数的部分lc.len[0]在加上u.cnt层覆盖后其覆盖次数的奇偶性取决于(0 u.cnt)的奇偶性即u.cnt的奇偶性。如果u.cnt是偶数那么这部分覆盖次数仍为偶数应加到u.len[0]如果是奇数则变为奇数应加到u.len[1]。同理从lc贡献的长度中原本覆盖次数为奇数的部分lc.len[1]在加上u.cnt层覆盖后其覆盖次数的奇偶性取决于(1 u.cnt)的奇偶性。1偶数奇数1奇数偶数。所以如果u.cnt是偶数lc.len[1]应加到u.len[1]如果是奇数则应加到u.len[0]。右孩子rc的贡献逻辑完全相同。因此节点u的信息合并公式为// 假设 u.cnt 的奇偶性已判断 bool cnt_is_odd (u.cnt 1); if (!cnt_is_odd) { // u.cnt 为偶数奇偶性不变 u.len[0] lc.len[0] rc.len[0]; u.len[1] lc.len[1] rc.len[1]; } else { // u.cnt 为奇数奇偶性翻转 u.len[0] lc.len[1] rc.len[1]; // 原来的奇数变偶数 u.len[1] lc.len[0] rc.len[0]; // 原来的偶数变奇数 }3. 懒标记的传递push_down当需要将当前节点的懒标记cnt下传给左右孩子时操作很简单直接将cnt值加到左右孩子的cnt上。然后根据新的cnt值重新计算左右孩子自身的len[0/1]对于孩子节点这就是上面提到的“叶子节点”或“非叶子节点”的更新逻辑需要通过一次push_up来完成。最后将当前节点的懒标记cnt清零。注意这里有一个非常重要的实现细节。在标准的区间赋值或叠加标记的线段树中push_down通常在递归进入子节点前调用。但在这道题里因为我们采用了“标记不下传仅在查询时通过cnt奇偶性影响合并”的策略即上面第2点我们其实可以不实现push_down这正是本题解法最巧妙的地方之一。 我们只在修改区间update时将cnt标记打在完全覆盖的节点上然后立刻push_up更新该节点的len[0/1]。在查询时我们其实不需要显式查询根节点的信息就是全局信息我们直接使用根节点的len[0/1]。由于cnt标记记录了该区间整体被多覆盖的层数在push_up过程中我们已经通过上述公式将cnt的影响融入了当前节点的len信息中。而当前节点的len信息在向其父节点合并时又会受到父节点cnt的影响。这样所有标记的影响在从下至上的push_up过程中被逐层正确处理无需显式下传。这大大简化了代码逻辑。3. 算法实现全流程与代码拆解理解了核心的数据结构维护逻辑我们就可以着手实现整个算法。我将结合代码一步步拆解每个环节的关键点和易错点。3.1 数据结构定义与离散化首先定义我们需要用到的所有数据结构和变量。#include iostream #include vector #include algorithm using namespace std; typedef long long LL; // 面积可能很大用 long long struct Segment { LL x1, y1, x2, y2; }; struct Event { LL y; // 事件发生的y坐标 LL x1, x2; // 事件影响的x区间 int flag; // 1 表示矩形下边进入-1表示矩形上边离开 Event(LL _y, LL _x1, LL _x2, int _f) : y(_y), x1(_x1), x2(_x2), flag(_f) {} // 按照y坐标排序 bool operator (const Event other) const { return y other.y; } }; // 线段树节点 struct Node { int l, r; // 离散化x坐标数组中的索引代表区间 [xs[l], xs[r]) int cnt; // 懒标记该区间被整体覆盖的次数 LL len[2]; // len[0]: 覆盖偶数次的长度len[1]: 覆盖奇数次的长度 } tr[N * 8]; // 线段树开4倍由于是区间索引且每个矩形产生两个x坐标所以大小要足够 vectorLL xs; // 用于离散化的x坐标数组 vectorEvent events; // 所有事件 vectorSegment segs; // 存储所有矩形 int n; // 矩形个数离散化是扫描线算法的标配目的是将连续的、值域可能很大的x坐标映射到连续的整数索引上便于线段树操作。void discrete() { xs.clear(); for (auto seg : segs) { xs.push_back(seg.x1); xs.push_back(seg.x2); // 注意这里存储的是x2代表区间右端点 } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); }这里有一个关键细节我们存储的是x2而不是x2-1之类的。因为我们的区间是左闭右开的[x1, x2)。离散化后线段树节点管理的区间是[xs[l], xs[r])其中r是索引xs[r]就是实际的右端点坐标。3.2 线段树的核心操作实现这是整个算法的引擎需要仔细实现。// 根据离散化数组计算节点u所代表区间的实际长度 LL interval_len(int u) { return xs[tr[u].r] - xs[tr[u].l]; } // 向上更新节点u的len信息 void push_up(int u) { // 如果当前区间有懒标记即被整体覆盖了cnt层 // 那么该区间的奇偶覆盖长度完全由cnt的奇偶性决定 if (tr[u].cnt 0) { // 注意cnt0 意味着整个区间至少被覆盖了cnt次。 // 我们需要根据cnt的奇偶性来设置len[0]和len[1] if (tr[u].cnt % 2 1) { // 奇数次覆盖 tr[u].len[1] interval_len(u); tr[u].len[0] 0; } else { // 偶数次覆盖 (包括cnt0吗不cnt0是前提) // 实际上当cnt为大于0的偶数时整个区间也是偶数次覆盖 tr[u].len[0] interval_len(u); tr[u].len[1] 0; } } else { // cnt 0 当前区间没有被整体覆盖的标记 // 那么它的信息需要由左右孩子合并而来 if (tr[u].l 1 tr[u].r) { // 叶子节点区间长度为0因为没有覆盖 tr[u].len[0] tr[u].len[1] 0; } else { int lc u 1, rc u 1 | 1; // 核心合并逻辑因为当前节点cnt0所以子节点的奇偶性就是最终奇偶性 tr[u].len[0] tr[lc].len[0] tr[rc].len[0]; tr[u].len[1] tr[lc].len[1] tr[rc].len[1]; } } // 等等上面的逻辑对吗仔细推敲一下我们发现有问题。 // 在push_up中我们不应该用tr[u].cnt来判断因为tr[u].cnt是懒标记。 // 我们之前推导的公式是父节点的len由子节点的len和父节点的cnt共同决定。 // 正确的push_up逻辑应该只依赖于子节点的len和当前节点的cnt。 // 我们需要修改一下。 } // 修正后的 push_up void push_up(int u) { // 清空当前节点的len tr[u].len[0] tr[u].len[1] 0; if (tr[u].l 1 tr[u].r) { // 叶子节点 if (tr[u].cnt 0) { // 有覆盖标记 if (tr[u].cnt 1) { tr[u].len[1] interval_len(u); } else { tr[u].len[0] interval_len(u); } } // 否则 len[0]和len[1]保持为0 } else { int lc u 1, rc u 1 | 1; // 非叶子节点信息由孩子合并而来 // 核心合并公式 if (tr[u].cnt 1) { // 当前节点有奇数层覆盖标记子节点的奇偶信息需要翻转后合并 tr[u].len[0] tr[lc].len[1] tr[rc].len[1]; tr[u].len[1] tr[lc].len[0] tr[rc].len[0]; } else { // 当前节点有偶数层或0层覆盖标记子节点的奇偶信息直接合并 tr[u].len[0] tr[lc].len[0] tr[rc].len[0]; tr[u].len[1] tr[lc].len[1] tr[rc].len[1]; } // 注意这里合并的是子节点在它们自身cnt影响下的len。 // 子节点的push_up会保证它们的len是正确的。 } // 特别地如果当前节点cnt0我们上面的合并逻辑还正确吗 // 考虑一个情况当前节点完全被覆盖(cnt0)那么无论子节点情况如何当前区间都应该全部是cnt次覆盖。 // 我们的合并逻辑是基于子节点len的如果cnt0子节点的len信息可能不准确因为子节点也有自己的cnt。 // 实际上当tr[u].cnt 0时意味着这个区间被整体“新增”了cnt层覆盖。 // 我们之前推导的公式正是处理这种情况用父节点的cnt去影响子节点汇总上来的奇偶信息。 // 所以上面的合并逻辑已经包含了cnt0的情况。因为公式中就是用cnt的奇偶性来决定是否翻转。 // 当cnt0时不翻转当cnt为奇数时翻转。 // 这个逻辑是统一的。 }push_up是灵魂务必理解透彻。接下来是建树和更新操作。// 建立线段树u是节点编号l和r是离散化x坐标数组中的索引 void build(int u, int l, int r) { tr[u] {l, r, 0, 0, 0}; if (l 1 r) { // 叶子节点区间长度为 xs[r] - xs[l] // len信息初始为0因为cnt0 return; } int mid (l r) 1; build(u 1, l, mid); build(u 1 | 1, mid, r); // 注意这里是 mid, r因为区间是左闭右开 // 建树时不需要push_up因为所有len初始为0且cnt0 } // 区间更新在区间 [ql, qr) 上增加 flag 层覆盖 // ql, qr 是离散化x坐标数组中的索引 void update(int u, int ql, int qr, int flag) { if (ql tr[u].l tr[u].r qr) { // 完全覆盖当前节点区间 tr[u].cnt flag; // 修改了cnt必须更新当前节点的len信息 push_up(u); return; } // 没有完全覆盖需要递归子区间 // 注意本题可以不push_down int mid (tr[u].l tr[u].r) 1; if (ql mid) update(u 1, ql, qr, flag); if (qr mid) update(u 1 | 1, ql, qr, flag); push_up(u); // 递归更新后需要根据子节点信息更新当前节点 }update操作是标准的线段树区间修改。由于我们采用了“标记永久化”的变体cnt标记留在节点上通过push_up的逻辑来体现其影响所以不需要push_down。这是代码简洁的关键。3.3 主算法流程与面积计算有了线段树主算法流程就清晰了。int main() { // 读入矩形数量 n cin n; segs.resize(n); for (int i 0; i n; i) { cin segs[i].x1 segs[i].y1 segs[i].x2 segs[i].y2; // 确保 x1 x2, y1 y2 if (segs[i].x1 segs[i].x2) swap(segs[i].x1, segs[i].x2); if (segs[i].y1 segs[i].y2) swap(segs[i].y1, segs[i].y2); } // 1. 离散化x坐标 discrete(); // 2. 构建事件 events.clear(); for (auto seg : segs) { // 找到x1, x2在离散化数组中的索引 int x1_idx lower_bound(xs.begin(), xs.end(), seg.x1) - xs.begin(); int x2_idx lower_bound(xs.begin(), xs.end(), seg.x2) - xs.begin(); // 下边事件flag 1 events.emplace_back(seg.y1, x1_idx, x2_idx, 1); // 上边事件flag -1 events.emplace_back(seg.y2, x1_idx, x2_idx, -1); } // 按y坐标排序事件 sort(events.begin(), events.end()); // 3. 建立线段树管理的x轴区间是 [0, xs.size()-1)注意是索引 // 线段树节点区间对应的是离散化x坐标的索引区间。 // 例如根节点 tr[1] 代表区间 [xs[0], xs[m-1])其中 m xs.size() int m xs.size(); build(1, 0, m - 1); // 注意build参数是索引我们管理的是 m-1 段小区间 // 4. 扫描线遍历 LL S_odd 0, S_even 0; LL pre_y events[0].y; // 第一条扫描线的y坐标 for (int i 0; i events.size(); i) { Event e events[i]; LL cur_y e.y; // 计算从上一条扫描线到当前扫描线之间的面积 if (i 0) { LL dy cur_y - pre_y; // 此时线段树根节点存储了当前x轴上覆盖次数为奇数和偶数的总长度 LL odd_len tr[1].len[1]; LL even_len tr[1].len[0]; // 注意未被覆盖的区域(len0)也属于偶数次覆盖它包含在len[0]中吗 // 是的。对于叶子节点当cnt0时len[0]和len[1]都是0。 // 在合并时这些长度为0的区间会被加总。所以根节点的len[0]包含了所有覆盖次数为偶数的区间长度包括0次。 // 因此总面积 odd_len * dy even_len * dy // 但更直接的是我们分别累加奇偶面积 S_odd odd_len * dy; S_even even_len * dy; } // 处理当前事件更新线段树 update(1, e.x1, e.x2, e.flag); // 更新pre_y pre_y cur_y; } // 5. 输出结果 cout S_odd endl S_even endl; return 0; }4. 关键细节、边界处理与调试心得理论完美代码清晰但真正上手实现时总会遇到一些“坑”。这里分享几个我调试过程中遇到的典型问题和解决方案。4.1 离散化索引与区间表示这是最容易出错的地方。我们离散化后得到xs数组例如xs {0, 5, 10, 20}。这代表了x轴上的3个区间[0, 5),[5, 10),[10, 20)。线段树节点中的l和r是xs数组的索引。例如一个节点u的tr[u].l 0,tr[u].r 2它代表的是原始坐标区间[xs[0], xs[2]) [0, 10)。在update操作中我们传入的ql和qr也是索引。例如我们要更新矩形x区间[5, 20)那么我们需要找到x15对应的索引ql1lower_bound找到xs[1]5x220对应的索引qr3lower_bound找到xs[3]20。然后调用update(1, 1, 3, flag)。线段树会更新索引区间[1, 3)对应的原始区间[xs[1], xs[3]) [5, 20)。易错点1建树范围build(1, 0, m-1)中的m是xs.size()。我们管理的是m个点构成的m-1个区间。所以根节点区间是[0, m-1)索引对应原始区间[xs[0], xs[m-1])。易错点2区间开闭务必坚持左闭右开[l, r)的原则。这意味着矩形的x区间是[x1, x2)。离散化存储的是x1和x2。线段树节点区间[l, r)对应[xs[l], xs[r])。在update递归时判断条件用if (ql mid)和if (qr mid)而不是或。4.2 线段树节点信息维护的再思考在push_up函数中我们用了统一的合并公式。但这里有一个隐藏的边界情况需要测试当cnt值很大时。我们的逻辑只依赖于cnt的奇偶性 (cnt 1)所以即使cnt累加到很大比如多次入边未出只要奇偶性正确结果就是对的。这是正确的因为覆盖层数的奇偶性只与总次数的奇偶性有关。但是我们必须确保cnt不会因为出边flag-1而变成负数。在矩形覆盖问题中一个合理的矩形序列先下边后上边保证了cnt始终 0。但在代码中我们还是应该确保update的调用顺序正确事件已按y排序这样就不会出现cnt为负的情况。如果出于严谨性考虑可以在push_up中取abs(cnt) 1但通常不需要。4.3 面积计算与“偶数次覆盖”的定义在面积计算部分我们使用了LL odd_len tr[1].len[1]; LL even_len tr[1].len[0]; S_odd odd_len * dy; S_even even_len * dy;这里even_len包含了覆盖次数为0、2、4...的区域。题目要求统计“偶数次覆盖”的面积覆盖0次当然属于偶数次。所以这个计算是正确的。一个验证方法是整个平面的总宽度total_width xs.back() - xs.front()。在扫描的任何时刻是否有odd_len even_len total_width理论上是的因为每个点要么被覆盖奇数次要么被覆盖偶数次包括0次。你可以在调试时输出这个等式来验证线段树维护的len信息是否正确。4.4 数据范围与溢出处理题目没有明确给出坐标范围但蓝桥杯国赛的数据往往很大。坐标值x, y和面积都可能超过int范围。因此所有坐标、长度、面积变量都应使用long long(LL)。离散化数组xs也应存储LL。在线段树节点中len[0]和len[1]也应是LL。在interval_len函数中计算xs[r] - xs[l]时xs是LL类型结果自然也是LL。4.5 测试用例设计自己构造测试用例是调试的最佳方式。可以从简单到复杂单个矩形(0,0,5,5)。结果应为S_odd 25,S_even 0整个平面面积设为5x525的话S_even应该是0不对平面是无限的我们只考虑矩形覆盖的区域。通常我们计算的是矩形覆盖区域的奇偶面积。对于单个矩形所有点被覆盖1次奇数次所以S_odd25,S_even0。但我们的算法计算的是当前扫描线之间的面积最终总和是对的。两个不重叠矩形(0,0,5,5)和(10,10,15,15)。每个矩形面积25都被覆盖1次。所以S_odd50,S_even0。两个完全重叠的矩形同一个矩形添加两次。所有点被覆盖2次偶数次。所以S_odd0,S_even25。两个部分重叠的矩形(0,0,10,10)和(5,5,15,15)。重叠区域为(5,5,10,10)面积25。在这个重叠区域覆盖次数为2偶数在其他非重叠区域覆盖次数为1奇数。可以手算验证。复杂嵌套和交错矩形设计多个矩形使得某些区域覆盖次数达到3、4等验证奇偶性计算的正确性。5. 性能分析与算法扩展5.1 时间复杂度分析设矩形数量为N。离散化O(N log N)。事件排序O(N log N)。扫描线过程有2N个事件每个事件触发一次线段树区间更新update复杂度为O(log M)其中M是离散化后x坐标点的数量M 2N。因此总时间复杂度为O(N log N)完全能够处理大规模数据。5.2 空间复杂度分析主要空间消耗在于存储矩形和事件O(N)。离散化数组O(N)。线段树需要开4 * M个节点M 2N所以是O(N)。 总体空间复杂度O(N)。5.3 算法扩展思考本题的“奇偶覆盖”是“统计覆盖k次面积”的一个特例。如果题目要求统计覆盖次数恰好为k的面积或者覆盖次数在某个区间[a, b]内的面积我们还能用类似方法吗对于更一般化的“覆盖k次面积”问题思路依然是维护每个区间内覆盖次数为0, 1, 2, ..., K的长度K是可能的最大覆盖次数不超过矩形个数N。这样每个节点需要维护一个长度为K1的数组len[]。在push_up时合并逻辑会变得更加复杂父节点的len[i]需要汇总所有子节点len[j]中满足(j cnt) % (K1) i的部分。这可以通过卷积或循环移位的思想来实现但复杂度会上升到O(K log N)每次更新。当K很大时如N很大这种方法就不太实用了。对于这种问题通常需要更复杂的数据结构或技巧。“奇偶覆盖”之所以优雅正是因为奇偶性只有两种状态我们可以用简单的“翻转”逻辑来处理将复杂度保持在O(log N)。这也体现了竞赛题目设计的一个特点在经典模型上增加一个巧妙的约束从而衍生出一个既需要扎实基础又需要灵活思维的新问题。回过头看这道题它的价值不仅在于让我们学会了一种新的线段树维护技巧更在于训练了我们一种重要的能力将问题的新约束奇偶性转化为数据结构可以维护的信息len[0]和len[1]并设计出相应的状态转移方程合并公式。这种“问题建模”和“数据结构设计”的能力是解决更复杂算法问题的基石。