第一次在在线评测系统上刷到编号 3642 这道《Get The Treasury》时我正处在扫描线从入门到进阶的过渡期。题面很简单给 n 个长方体求被至少 3 个长方体共同覆盖的总体积。解法看起来也不复杂四个字概括扫描线 体积交。可真当自己动手写才发现三维场景里的扫描线远比二维面积并复杂光是如何把体积交拆成可计算的形式就卡了我大半天。更别提网上能找到的题解要么只有一句核心思路要么贴一段没有注释的代码看完照样一脸懵。这篇文章就是我把这道题彻底吃透后的完整复盘。我会从题目到底在算什么讲起再到降维思路、线段树维护覆盖三次的原理最后给出一份带详细注释的可运行代码和我的踩坑记录。适合已经会一维扫描线、想进阶覆盖类问题的选手也适合所有想知道三维体积交为什么能用二维方法做的读者。1. 先弄清楚题目到底要算什么三个关键词一个都不能错1.1 题面里最容易忽略的判定条件题目给的每个长方体由两个对角顶点决定比如(x1,y1,z1)和(x2,y2,z2)。通常题目会保证x1x2、y1y2、z1z2但部分版本不保证稳妥的读入方式是用 min/max 把两个顶点归一化成左下后和右上前。这个细节不影响算法主体但写代码时不注意后面所有判断都会出问题。真正容易被忽略的是至少 3 个长方体共同覆盖这个条件。它不是体积并也不是严格意义的体积交。体积并要求覆盖次数1普通体积交通常要求2这道题是3。换句话说我们要计算的区域是空间中某个小体积元当且仅当它被 3 个或更多长方体同时盖住时才计入答案。这个阈值 3 让题目有了层次感。如果只要求1一个len1就够2需要len23就需要len3。这也是为什么很多二维扫描线模板只维护一个覆盖长度而这题必须在线段树里同时维护三种长度因为它本质上是一个覆盖次数分级统计的问题。1.2 为什么坐标范围大但 n 不大决定了算法方向这题的数据特点通常是 n ≤ 1000而坐标值可以到 1e9 量级。这种顶点少、坐标稀疏且数值大的组合决定了不可能用三维差分或三维前缀和暴力做——如果坐标范围只有 0 到 100直接开一个 101×101×101 的数组就能处理但坐标到 1e9 时任何按坐标单位枚举的思路都是死路。坐标范围大但顶点数有限意味着必须用离散化配合扫描线段树。所有长方体的 2n 个 z 坐标、2n 个 y 坐标最多各产生 2000 个不同的坐标值这个规模线段树完全可以承受。所以看到大坐标先别慌真正决定复杂度的不是坐标值的大小而是顶点的数量。2. 降维的钥匙z轴切片让三维体积问题退化成二维面积问题2.1 三维体积公式与薄片法的等价性三维体积交最朴素的计算办法是积分。设A(z)表示在高度 z 处水平截面上被至少 3 个长方体覆盖的二维面积那么总体积就是∫ A(z) dz。这里的A(z)是随 z 变化的阶梯函数。因为所有长方体的面都平行于坐标平面长方体在 z 方向的边界只发生在它的 z1 和 z2 处所以只要把所有 z1、z2 收集起来排序去重得到一组 z 值那么在任意两个相邻 z 值之间的开区间内所有长方体的覆盖关系都不会发生变化。换句话说A(z)在每个薄片内是一个常数。这样体积积分就退化成了有限段求和把每段薄片的高度乘上该段薄片内的A(z)累加即可。边界点本身的测度为零对体积没有贡献所以可以放心地只关心开区间内的覆盖状态。2.2 离散化z坐标之后每个薄片内部发生了什么具体做法是把所有长方体的 z1 和 z2 收集进一个数组排序去重。假设得到z[0] z[1] ... z[m-1]那就有m-1个薄片第i个薄片是[z[i], z[i1]]。对于每个薄片我们要找出完全覆盖这个薄片的长方体。判断条件是c.z1 z[i] c.z2 z[i1]注意这个条件是完全覆盖而不是相交。如果一个长方体只和薄片部分重叠比如它的 z 范围是(1,3)而当前薄片是(2,4)那它只覆盖了薄片的一半高度。此时若把它投影到 xy 平面投影矩形会铺满整个薄片的 xy 范围我们会误以为它在整个薄片高度上都存在结果就会多算体积。所以必须严格使用完全覆盖判断这是这道题最容易踩的坑之一。这些通过筛选的长方体在每个薄片上只表现为 xy 平面上的一个投影矩形。于是问题被成功降维对每个薄片计算这些投影矩形中被至少覆盖 3 次的总面积再乘上薄片高度累加进答案。2.3 薄片内投影问题的形式和复杂度预估单看一个薄片任务变成了给定若干个矩形求平面上被至少 3 个矩形覆盖的面积。这正是最经典的二维扫描线问题只是在更新线段树时要同时维护三种覆盖长度。整体复杂度要算一算。z 薄片数量最多2n-1个每个薄片内要遍历所有 n 个长方体做筛选然后对最多2n个竖边事件排序并做线段树更新。单层复杂度O(n log n)总复杂度O(n^2 log n)。n1000 时大约是1000 * 1000 * 10 10^7量级完全可以在时限内跑完。这个复杂度模型也解释了为什么这道题敢把 n 放到 1000平方复杂度配合 log是扫描线类题目的常见套路。3. 线段树如何同时记住覆盖1次、2次、3次的长度3.1 扫描线上要维护的三种长度回到二维扫描线的基本操作把每个矩形拆成左右两条竖边左竖边代表进入右竖边代表离开。从左到右扫描 x 轴线段树维护的是当前 x 处 y 方向的覆盖情况。每移动一段距离就用当前覆盖长度乘以移动的 Δx累加进面积。在本题中覆盖长度必须区分等级len1表示 y 方向上至少被覆盖 1 次的长度len2表示至少被覆盖 2 次的长度len3表示至少被覆盖 3 次的长度。计算面积时用的是len3因为只有覆盖次数达到 3 的区域才计入答案。3.2 覆盖次数cnt和len1/len2/len3的推演表格线段树每个节点需要记录两个东西一个是cnt代表当前节点整个区间被完整覆盖了几次另一个是len1、len2、len3分别代表这个节点区间内达到对应覆盖次数的实际长度。这里有一个关键约定cnt不向下传递到子节点它只代表当前节点区间作为一个整体被覆盖的次数。一个位置的真实覆盖次数等于从根到叶子路径上所有cnt之和。根据当前节点cnt的取值以及左右孩子的len1、len2、len3可以推导出当前节点的三个长度。下表是完整的推演逻辑当前节点cntlen1len2len3cnt 3区间全长区间全长区间全长cnt 2区间全长区间全长左右孩子len1之和cnt 1区间全长左右孩子len1之和左右孩子len2之和cnt 0左右孩子len1之和左右孩子len2之和左右孩子len3之和每一行背后的逻辑都很直白。cnt 3时整个区间已经被至少 3 个矩形完整覆盖所以三个长度都等于全长。cnt 2时区间整体已经有 2 层覆盖任何子区间只要再被覆盖 1 次就能达到 3 次所以len3等于左右孩子中至少覆盖 1 次的长度之和而len1、len2自然都是全长。cnt 1时区间整体只有 1 层子区间需要至少覆盖 2 次才能凑够 3 次所以len3用孩子的len2汇总len2用孩子的len1汇总len1仍然是全长。cnt 0时当前节点没有任何整体覆盖所有长度都直接来自左右孩子的汇总。叶子节点没有孩子所以cnt 2或cnt 1时孩子相关的那项长度就是 0。代码里必须单独处理l r的情况否则访问不存在的孩子节点会得到错误结果甚至越界。3.3 为什么这里不需要pushdown很多读者看到这里会问区间更新不做 pushdown那孩子的cnt不是不准吗确实不准但这不影响答案因为我们只查询根节点的总长度并不查询某个具体点。可以把每个节点想成公寓楼的楼层管理员。cnt相当于管理员在自己本子上记这一层整体被租了几遍而不是把人数分配到每个房间。当我们要知道整栋楼有多少房间达到某个覆盖次数时从顶层往下叠加每层记录的整体租用次数就够用了。只有在需要精确查询某个房间的使用情况时才必须把记录一层层下放到房间也就是 pushdown。扫描线问题只在区间整体做增减并且永远只查询根节点所以不需要 pushdown。这个技巧避免了在进入和离开事件来回交替时反复下传状态的巨大开销也让代码简洁不少。理解这一点比背代码重要得多。4. 完整实现事件构造、离散化、主循环与手算验证4.1 数据结构和事件的定义先定义三个结构体。Cube存长方体Event表示扫描线上的竖边事件SegTree是线段树节点。注意线段树的len1、len2、len3存的是真实坐标长度所以在 pushUp 中需要用到 y 坐标离散化数组来算区间长度。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 2010; struct Cube { int x1, y1, z1, x2, y2, z2; }; struct Event { int x, y1, y2, type; // type 1 表示进入-1 表示离开 bool operator (const Event other) const { return x other.x; } }; struct SegTree { int cnt; int len1, len2, len3; }; SegTree tree[MAXN 2]; int yVal[MAXN]; // y坐标离散化数组这里yVal的作用是线段树某个节点若代表 y 区间[l, r]它对应的真实长度是yVal[r1] - yVal[l]。也就是说线段树的下标是 y 区间的编号而不是 y 坐标点的编号这点非常容易混。4.2 主循环同一x上的事件必须一口气处理完扫描线主循环的写法很多我推荐这种先取出当前 x把当前 x 上的所有事件一次性更新进线段树再计算从当前 x 到下一个 x 的面积增量。void update(int o, int l, int r, int ql, int qr, int val) { if (ql r || qr l) return; if (ql l r qr) { tree[o].cnt val; pushUp(o, l, r); return; } int mid (l r) 1; if (ql mid) update(o 1, l, mid, ql, qr, val); if (qr mid) update(o 1 | 1, mid 1, r, ql, qr, val); pushUp(o, l, r); } ll solveOneZSlice(int zL, int zR, const vectorCube cubes) { vectorEvent events; vectorint yVec; for (const Cube c : cubes) { if (c.z1 zL c.z2 zR) { events.push_back({c.x1, c.y1, c.y2, 1}); events.push_back({c.x2, c.y1, c.y2, -1}); yVec.push_back(c.y1); yVec.push_back(c.y2); } } if (events.empty()) return 0; sort(yVec.begin(), yVec.end()); yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end()); int segCnt (int)yVec.size() - 1; if (segCnt 0) return 0; for (int i 0; i (int)yVec.size(); i) yVal[i] yVec[i]; sort(events.begin(), events.end()); memset(tree, 0, sizeof(tree)); ll area 0; int i 0; while (i (int)events.size()) { int curX events[i].x; while (i (int)events.size() events[i].x curX) { int ql lower_bound(yVec.begin(), yVec.end(), events[i].y1) - yVec.begin(); int qr lower_bound(yVec.begin(), yVec.end(), events[i].y2) - yVec.begin() - 1; if (ql qr) update(1, 0, segCnt - 1, ql, qr, events[i].type); i; } if (i (int)events.size()) { int nextX events[i].x; area (ll)(nextX - curX) * tree[1].len3; } } return area * (ll)(zR - zL); }为什么要把同一个 x 的所有事件先全部处理完因为扫描线在 xcurX 处的状态必须同时反映所有在该 x 上发生的进入和离开。如果只处理了一半事件就开始计算面积覆盖状态没有达到稳态算出的面积就偏了。使用这段代码的写法所有同 x 事件在同一个 while 内完成更新随后才累加面积逻辑最稳。4.3 手算一个三层重叠的小样例为了确认代码逻辑我构造一个能完全手算的小样例。三个长方体A: (0,0,0) 到 (2,2,2)B: (0,0,0) 到 (2,2,2)C: (1,1,1) 到 (3,3,3)z 坐标排序去重后是 0,1,2,3切出三个薄片薄片 [0,1]C 不满足完全覆盖条件因为c.z11 0。只有 A、B 覆盖最多覆盖 2 层len30贡献 0。薄片 [1,2]A、B、C 都完全覆盖。xy 投影上A、B 是[0,2]x[0,2]C 是[1,3]x[1,3]。至少覆盖 3 次的区域是[1,2]x[1,2]面积 1薄片高度 1贡献体积 1。薄片 [2,3]A、B 不满足完全覆盖条件因为c.z22 3。只有 C 覆盖贡献 0。总答案就是 1。这个例子虽然简单但完整覆盖了进入、离开、筛选条件、三层覆盖这几个核心要素我每次改完代码第一件事就是拿它验证。4.4 完整可运行代码下面给出一份完整代码包含了 pushUp 的四种情况处理和 main 函数中的多组测试逻辑。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 2010; struct Cube { int x1, y1, z1, x2, y2, z2; }; struct Event { int x, y1, y2, type; bool operator (const Event other) const { return x other.x; } }; struct SegTree { int cnt; int len1, len2, len3; }; SegTree tree[MAXN 2]; int yVal[MAXN]; void pushUp(int o, int l, int r) { int total yVal[r 1] - yVal[l]; if (tree[o].cnt 3) { tree[o].len1 tree[o].len2 tree[o].len3 total; } else if (tree[o].cnt 2) { tree[o].len1 tree[o].len2 total; if (l r) tree[o].len3 0; else tree[o].len3 tree[o 1].len1 tree[o 1 | 1].len1; } else if (tree[o].cnt 1) { tree[o].len1 total; if (l r) tree[o].len2 tree[o].len3 0; else { tree[o].len2 tree[o 1].len1 tree[o 1 | 1].len1; tree[o].len3 tree[o 1].len2 tree[o 1 | 1].len2; } } else { if (l r) tree[o].len1 tree[o].len2 tree[o].len3 0; else { tree[o].len1 tree[o 1].len1 tree[o 1 | 1].len1; tree[o].len2 tree[o 1].len2 tree[o 1 | 1].len2; tree[o].len3 tree[o 1].len3 tree[o 1 | 1].len3; } } } void update(int o, int l, int r, int ql, int qr, int val) { if (ql r || qr l) return; if (ql l r qr) { tree[o].cnt val; pushUp(o, l, r); return; } int mid (l r) 1; if (ql mid) update(o 1, l, mid, ql, qr, val); if (qr mid) update(o 1 | 1, mid 1, r, ql, qr, val); pushUp(o, l, r); } ll solveOneZSlice(int zL, int zR, const vectorCube cubes) { vectorEvent events; vectorint yVec; for (const Cube c : cubes) { if (c.z1 zL c.z2 zR) { events.push_back({c.x1, c.y1, c.y2, 1}); events.push_back({c.x2, c.y1, c.y2, -1}); yVec.push_back(c.y1); yVec.push_back(c.y2); } } if (events.empty()) return 0; sort(yVec.begin(), yVec.end()); yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end()); int segCnt (int)yVec.size() - 1; if (segCnt 0) return 0; for (int i 0; i (int)yVec.size(); i) yVal[i] yVec[i]; sort(events.begin(), events.end()); memset(tree, 0, sizeof(tree)); ll area 0; int i 0; while (i (int)events.size()) { int curX events[i].x; while (i (int)events.size() events[i].x curX) { int ql lower_bound(yVec.begin(), yVec.end(), events[i].y1) - yVec.begin(); int qr lower_bound(yVec.begin(), yVec.end(), events[i].y2) - yVec.begin() - 1; if (ql qr) update(1, 0, segCnt - 1, ql, qr, events[i].type); i; } if (i (int)events.size()) { int nextX events[i].x; area (ll)(nextX - curX) * tree[1].len3; } } return area * (ll)(zR - zL); } int main() { int T; scanf(%d, T); for (int caseNo 1; caseNo T; caseNo) { int n; scanf(%d, n); vectorCube cubes(n); vectorint zVec; for (int i 0; i n; i) { scanf(%d%d%d%d%d%d, cubes[i].x1, cubes[i].y1, cubes[i].z1, cubes[i].x2, cubes[i].y2, cubes[i].z2); if (cubes[i].x1 cubes[i].x2) swap(cubes[i].x1, cubes[i].x2); if (cubes[i].y1 cubes[i].y2) swap(cubes[i].y1, cubes[i].y2); if (cubes[i].z1 cubes[i].z2) swap(cubes[i].z1, cubes[i].z2); zVec.push_back(cubes[i].z1); zVec.push_back(cubes[i].z2); } sort(zVec.begin(), zVec.end()); zVec.erase(unique(zVec.begin(), zVec.end()), zVec.end()); ll ans 0; for (int i 0; i 1 (int)zVec.size(); i) { ans solveOneZSlice(zVec[i], zVec[i 1], cubes); } printf(Case %d: %lld\n, caseNo, ans); } return 0; }这份代码我建议直接抄下来跑一遍样例再改成自己的风格。核心的 pushUp 和主循环部分可以一字不改因为覆盖次数分级的推导是固定的。5. 调试实录我在这道题上踩过的坑以及每步怎么排查5.1 坑1z切片条件写成相交而不是完全覆盖这是我犯的第一个错。最开始我把筛选条件写成c.z1 zR c.z2 zL觉得只要有交集就参与这个薄片的计算。结果用简单的三层样例验证时答案偏大。排查过程我先是怀疑线段树写错了打印每个薄片内参与的长方体编号发现薄片 [0,1] 里居然有 C。可 C 的 z 范围是(1,3)它只覆盖薄片的一半高度投影却在薄片里被当作了全程覆盖。改成c.z1 zL c.z2 zR后答案正确。这个坑的教训是三维降二维时这个长方体在这一层是否存在必须用完全覆盖来判断不能用相交。5.2 坑2同一x事件的处理顺序混乱我最初的主循环是每处理一个事件就立刻计算到下一个 x 的面积。大多数扫描线题目可以这么写但在这题里如果同一个 x 上既有进入又有离开先处理哪个会产生不同结果。举一个浅显的例子x2 处同时有一个矩形的右边界离开和另一个矩形的左边界进入覆盖次数应当先同时应用这两个变化再计算后续面积。如果先处理离开再算增量中间状态就会少一层覆盖。改动后的代码采用同 x 事件全部先更新再统一计算到下一个 x 的增量这个问题彻底消失。排查这个坑时比较笨的方法是把每个 x 处的 tree[1].len3 打印出来对照手算的覆盖长度很快能定位问题。5.3 坑3离散化下标到底是点还是段y 方向离散化后如果有 m 个不同 y 值实际只有 m-1 个 y 区间。线段树的叶子代表的是一个区间段而不是一个坐标点。我在初版代码中把qr lower_bound(...) - 1这一句漏了导致每个事件更新的 y 范围整体右移一个区间边界上的覆盖长度全部错位。调试时最有效的办法是构造只有两个矩形的场景手动打印 update 操作覆盖的 [ql, qr]对比预期。这里也提醒读者在写 pushUp 时节点实际长度用yVal[r1] - yVal[l]如果误写成yVal[r] - yVal[l]最后一个区间的长度会变成 0答案也会悄悄变小。5.4 坑4数据类型和中间乘法溢出坐标值大时单个体积就可能超过 int 范围所以面积和答案都用 long long。但仍有一个隐蔽点area * (zR - zL)中zR - zL是 int若 area 是 long long会自动提升没问题。可如果把zR - zL先存进 int 再乘在某些极限数据下就会溢出为负数导致答案异常。我用printf(%lld)输出答案曾经图省事写成%d结果正确结果被打成乱码第一反应以为是算法错了白调试了半天。建议在本地把编译器的 warning 开到最大这类格式错误能提前暴露。5.5 坑5多组数据的状态残留这道题是多组数据线段树数组是全局变量。如果每组数据开始前不执行memset(tree, 0, sizeof(tree))上一组残留的 cnt 会混进下一组的计算结果中。这种错误很隐蔽因为答案往往只是偏大一点点不仔细看根本发现不了。我的排查手段是在每组数据的开头打印一次tree[1].len1发现不是 0 就说明没清干净。加了 memset 之后一切正常。另外yVal 数组也必须在每个薄片处理前重新赋值我把它放在solveOneZSlice内部避免跨薄片串值。把上面的坑总结成一张表方便读者自查现象可能原因解决办法答案偏大z切片用了相交判断改用完全覆盖c.z1 zL c.z2 zR边界处面积少算同x事件未处理完就计算增量同一x全部更新后再累加面积覆盖长度整体错位离散化点下标误当段下标明确线段树下标为区间编号输出为负数或乱码int溢出或格式符错误全程long long用%lld输出多组数据答案混乱全局线段树未清零每组开始memset最后分享一点个人体会。做完这道题再回头看二维扫描线很多原来靠硬记的写法突然就通了比如为什么会有一个cnt数组、为什么 pushUp 要从孩子汇总、为什么排序后要先更新再算增量背后都是覆盖次数这个状态本身。建议先把只维护len1的二维面积并题做熟再来啃这道需要len1、len2、len3的三维版本否则很容易在多层状态中迷失。如果以后遇到求至少 k 次覆盖体积的题只需要把 pushUp 里的长度数组扩到 k 维其余结构完全不用动。这个可扩展性就是这道题留给我们最实在的价值。