HDU 3642 Get The Treasury第一次在题单里看到这个标题后面跟着“扫描线 体积交”我第一反应是三维数据结构难题。真正动手做下来才发现它考的不是三维线段树而是如何把三维体积问题用 z 方向切片降成二维扫描线再用线段树维护覆盖次数。题意其实一句话就能讲完给你最多 1000 个轴对齐的长方体求空间中至少被 3 个长方体同时覆盖的体积。这篇文章就从读题开始把完整的推导、代码实现和踩坑记录整理出来希望能帮到正在被这道题折磨的人。1. 先读懂题目这题到底在求什么1.1 不是体积并也不是严格的体积交很多人看到“体积交”三个字第一反应是求一堆长方体的公共部分类似若干个长方体求交集边长。但 HDU 3642 说的其实是另一件事空间中任意一个点统计它落在多少个长方体内部如果这个数字大于等于 3那么这个点就是对答案有贡献的点所有这类点构成的集合的体积就是答案。换句话说这里求的是覆盖次数达到 3 及以上的体素集合体。它不要求同一组三个长方体始终固定可能是 A、B、C 三个叠在一起也可能是 B、C、D 三个叠在一起还可能出现 A、B、C、D 四个一起覆盖。只要某个位置的覆盖次数不少于 3就算进去。用二维来类比就很容易理解平面上三个矩形互相交叠交叠区域里如果有三个矩形都盖住的地方那就是“覆盖次数 3 的面积”。三维只是把矩形换成轴对齐长方体把面积换成体积。1.2 数据范围决定了暴力不可行题目限制 n 最大 1000坐标范围是 0 到 10^6都是整数。如果按最暴力的思路把三维空间切成一个个单位立方体再统计每个立方体被多少个长方体覆盖那空间规模是 10^18 量级直接不可能。体积上限也要注意。单个长方体体积最大能到 10^18虽然答案不会超过整个 1e6 立方体的体积也就是最多 10^18 左右但已经超过了 int 范围所以所有面积和体积相关的累加必须用 long long。这是很多新手在本地能过样例、提交却 WA 的一个隐藏原因。1.3 前置知识二维矩形面积并扫描线在接触这道题之前最好先熟悉经典问题矩形面积并。做法是把每个矩形拆成两条竖直边一条是入边对 y 方向覆盖次数 1一条是出边对 y 方向覆盖次数 -1所有边按 x 坐标排序。扫描线从 x 轴左往右移动同时用线段树维护当前 x 位置被哪些 y 区间覆盖以及有效覆盖长度。每次移动到下一个事件 x 位置时相邻宽度乘以当前覆盖长度累加面积。HDU 3642 的 xy 平面部分其实也是这套东西只不过维护的不是“覆盖长度 1”而是“覆盖长度 3”。所以如果能把二维面积并的线段树写法吃透三维部分只是多套一层 z 方向切片。2. 核心思路把体积问题切成一片一片算2.1 为什么可以用 z 轴切片长方体都是轴对齐的并且每个长方体的 z 坐标由 z1 和 z2 给出。把所有出现过的 z1、z2 收集起来排序去重最多得到 2n 个不同的 z 坐标。这些坐标把 z 轴切成若干个相邻区间例如 [z0, z1)、[z1, z2) 等等。关键在于在任意一个相邻 z 区间内部任何一个长方体要么完全贯穿这个区间要么完全不碰这个区间。因为长方体在 z 方向是连续的不会出现“在区间中间突然开始或结束”的情况区间的端点是所有长方体 z 边界的排序点。所以对于固定一个 z 切片每个长方体在 xy 平面的投影是否对这个切片有贡献是恒定不变的。于是三维体积问题被拆成两层先固定一个 z 切片算出该切片内 xy 平面上“覆盖次数 3”的面积再乘以切片的厚度 dz累加所有切片体积就是答案。这就是经典的“降维”处理也是这道题叫“扫描线 体积交”的原因。2.2 每个 z 区间怎么提取矩形假设当前处理的是相邻 z 区间 [zl, zr)其中 zl zs[i]zr zs[i1]注意是左闭右开。遍历所有长方体如果一个长方体满足c.z1 zl c.z2 zr那说明在 z 方向上这个长方体完全覆盖了当前薄片。此时把它投影到 xy 平面形成一个矩形Rect{ c.x1, c.y1, c.x2, c.y2 }所有满足条件的矩形构成当前 z 切片的矩形集合。然后对这些矩形在 xy 平面上跑一次线段树扫描线求出覆盖 3 次及以上的面积乘以 (zr - zl)就是这个切片对体积的贡献。2.3 为什么必须是“完全贯穿”有同学会想如果长方体只覆盖了 z 区间的一部分是不是也能按比例折算贡献不能。这个 z 切片是完整的离散单元如果长方体只盖住左边一半那它的 xy 投影并不是在整个切片内都有恒定覆盖直接把投影当成一个完整矩阵会高估体积。实际上这种“完全贯穿才能提取矩形”的思路是这道题能成立的根基。因为 z 区间长度是我们手动离散出来的任何长方体要么完全盖住它要么从它的某个边界点截断。只要它没有完全盖住它在这个切片内的覆盖就不是均匀的不能放进统一的 xy 扫描线里处理。2.4 复杂度估算z 坐标去重后最多有 2n 个对应最多 2n - 1 个有效切片n 1000 时大约 2000 个切片。每个切片枚举 n 个长方体构造矩形再对这些矩形做一次扫描线。矩形数量最多 1000线段树的 y 离散点最多也是 2000 个单次扫描线复杂度约 O(n log n) 量级。整体约 2000 * 1000 * log(2000)大概在 10^7 到 10^8 的操作量级在老题的时间限制下是可以接受的。3. 线段树维护“至少三次”的细节3.1 扫描线事件与线段树的关系把矩形拆成事件在 x x1 处y 区间 [y1, y2) 覆盖次数 1在 x x2 处y 区间 [y1, y2) 覆盖次数 -1。线段树的叶子节点对应 y 离散坐标之间的区间每个节点维护一定 y 范围内的覆盖信息。扫描过程里两个相邻事件 x 坐标之间的宽度是稳定的此时 y 方向的覆盖信息由线段树根节点的 len3 给出。只要在每次事件更新之前先把上一个宽度累加进面积就能算出整个面积。3.2 节点需要维护哪些字段经典矩形面积并只需要维护一个 cnt 和一个 len这里要扩展到三份长度cnt当前节点代表的整个区间被完整覆盖的次数。注意这是懒惰式标记只记录“整段都加了几次”不往下传给子节点。len1这个区间内实际覆盖次数 1 的 y 长度。len2这个区间内实际覆盖次数 2 的 y 长度。len3这个区间内实际覆盖次数 3 的 y 长度。根节点的 len3 就是当前 x 位置下xy 平面中至少被覆盖 3 次的 y 方向总长度。面积累加时直接用根节点的 len3 乘以宽度。3.3 pushUp 的完整推导线段树更新完子节点或者某个节点自身 cnt 发生变化后都需要 pushUp 重新计算 len1、len2、len3。推导的核心是当前节点本身有 cnt 次“整段覆盖”这些次数作用于整个区间而子节点里记录的 len 值表示子区间内“额外”的覆盖情况。分情况讨论情况一cnt 3。整个区间已经被完整覆盖了至少 3 次所以无论子区间内部情况如何整个区间的任意一段覆盖次数都不小于 3三个长度都等于区间总长度。情况二cnt 2。整个区间至少被覆盖 2 次所以 len1 和 len2 都等于区间总长度。但要达到 3 次还需要看子区间内部是否有至少 1 次额外覆盖因此 len3 左子节点 len1 右子节点 len1。情况三cnt 1。整个区间至少被覆盖 1 次len1 等于区间总长度。要达到 2 次需要子区间内有至少 1 次额外覆盖所以 len2 左子节点 len1 右子节点 len1。要达到 3 次需要子区间内有至少 2 次额外覆盖所以 len3 左子节点 len2 右子节点 len2。情况四cnt 0。整个区间没有额外整段覆盖直接合并左右子节点的三个 len 即可。叶子节点没有子节点情况二和情况三中“子节点”不存在所以 len2、len3 直接置 0。情况一不受影响len1、len2、len3 都等于区间总长度因为如果一个叶子区间被覆盖 3 次它的三份长度当然都是完整的区间长度。这个推导一定要理解到位不能死记。最容易写错的是情况三里 len2 和 len3 都跟左子节点的 len1、len2 有关而不是根节点自己的 len1。3.4 区间离散化与下标映射y 坐标离散化之后用 ys 数组存放所有 y1、y2。线段树的叶子节点 [i, i1) 代表实际 y 区间 [ys[i], ys[i1])长度为 ys[i1] - ys[i]。所以节点 l 到 r 的总长度是 ys[r] - ys[l]而不是 r - l。更新一个矩形时通过 lower_bound 找到 y1、y2 在 ys 数组中的下标 ql、qr。注意 qr 就是右端点的下标更新区间是 [ql, qr)。线段树节点完全覆盖的条件是 ql l r qr这里的 r 是右端点下标可以等于 qr因为我们维护的是左闭右开的离散区间。这个细节一旦弄错会出现边界上的覆盖偏差小数据可能看不出来大数据就会错。4. 完整实现与主流程4.1 数据结构与辅助函数我直接用结构体存长方体事件结构体存扫描线竖边。线段树用数组实现每个节点包含 cnt、len1、len2、len3 四个字段。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 2005; struct Cube { int x1, y1, z1, x2, y2, z2; }; struct Rect { int x1, y1, x2, y2; }; struct Event { int x, y1, y2, add; bool operator(const Event other) const { return x other.x; } }; vectorint ys; // y 方向离散化数组 struct SegNode { int cnt; int len1, len2, len3; } tree[MAXN 2];4.2 pushUp 与 updatepushUp 按上面推导的五种情况写。update 区间完全覆盖时只修改 cnt再调用 pushUp否则递归到子节点后重新 pushUp。void pushUp(int o, int l, int r) { if (tree[o].cnt 3) { tree[o].len1 tree[o].len2 tree[o].len3 ys[r] - ys[l]; } else if (tree[o].cnt 2) { tree[o].len1 tree[o].len2 ys[r] - ys[l]; if (l 1 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 ys[r] - ys[l]; if (l 1 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 1 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 v) { if (ql l r qr) { tree[o].cnt v; pushUp(o, l, r); return; } if (l 1 r) return; // 叶子且未被完全覆盖说明更新区间与之不相交 int mid (l r) 1; if (ql mid) update(o 1, l, mid, ql, qr, v); if (qr mid) update(o 1 | 1, mid, r, ql, qr, v); pushUp(o, l, r); }update 里那个叶子判断很重要。因为当节点是叶子且更新区间没有完全覆盖它时说明这个叶子与更新区间没有交集直接返回否则会访问到不存在的子节点导致越界。4.3 面积计算函数calcArea 接收当前 z 切片的所有矩形把它们拆成事件按 x 排序然后扫描累加根节点 len3 乘以宽度。ll calcArea(vectorRect rects) { if (rects.empty()) return 0; vectorEvent ev; for (auto r : rects) { ev.push_back({r.x1, r.y1, r.y2, 1}); ev.push_back({r.x2, r.y1, r.y2, -1}); } sort(ev.begin(), ev.end()); memset(tree, 0, sizeof(tree)); ll area 0; for (int i 0; i (int)ev.size(); i) { if (i 0) { int width ev[i].x - ev[i - 1].x; area 1LL * tree[1].len3 * width; } int y1 lower_bound(ys.begin(), ys.end(), ev[i].y1) - ys.begin(); int y2 lower_bound(ys.begin(), ys.end(), ev[i].y2) - ys.begin(); update(1, 0, (int)ys.size() - 1, y1, y2, ev[i].add); } return area; }注意每次调用 calcArea 前清空线段树。因为每次 z 切片的矩形集合都是全新的线段树必须从全 0 状态开始。这里的 ys 数组是全局的包含所有输入长方体的 y 坐标所以 lower_bound 一定能找到 y1 和 y2。如果担心局部更干净也可以在 calcArea 内部自己收集 ys但没必要。4.4 主流程与 z 枚举主流程先读入所有长方体收集 z 坐标和 y 坐标到全局数组。然后枚举相邻 z 坐标对每个切片筛选矩形累加体积。int main() { int T; scanf(%d, T); for (int kase 1; kase T; kase) { int n; scanf(%d, n); vectorCube cubes(n); vectorint zs; ys.clear(); 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); ys.push_back(cubes[i].y1); ys.push_back(cubes[i].y2); zs.push_back(cubes[i].z1); zs.push_back(cubes[i].z2); } sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); sort(zs.begin(), zs.end()); zs.erase(unique(zs.begin(), zs.end()), zs.end()); ll ans 0; for (int i 0; i 1 (int)zs.size(); i) { int zl zs[i], zr zs[i 1]; vectorRect rects; for (auto c : cubes) { if (c.z1 zl c.z2 zr) { rects.push_back({c.x1, c.y1, c.x2, c.y2}); } } if (!rects.empty()) { ans calcArea(rects) * 1LL * (zr - zl); } } printf(Case %d: %lld\n, kase, ans); } return 0; }整个代码核心就是这句对每个 z 切片选出所有完全覆盖该切片的长方体投影成矩形用 calcArea 算出覆盖 3 次以上的面积乘以切片厚度。三维体积问题到这里已经完整转化成一维方向的枚举加上二维扫描线。5. 踩坑记录与调试经验5.1 pushUp 是最容易写错的地方我第一版 pushUp 在 cnt 2 的时候把 len3 写成了左右子节点的 len3 之和样例直接错。稍微想一下就明白当前节点已经整段覆盖 2 次子节点只要额外覆盖 1 次总覆盖次数就达到 3所以应该取子节点的 len1而不是 len3。同理 cnt 1 时len3 应该取子节点 len2而不是 len1。这种推导不是背下来就行一定要能自己推出来。把它想成一个层层叠加的过程当前节点自带 cnt 层底子节点内部的覆盖次数是额外叠上去的。需要达到 k 层就看子节点里额外覆盖至少 k - cnt 层的长度。5.2 z 区间边界条件的等号判断长方体是否覆盖 z 切片时我用 c.z1 zl c.z2 zr。很多同学写成 c.z2 zr觉得右边界是开区间就不该包含等号。实际上离散出来的 zr 是下一个 z 坐标当前切片是 [zl, zr)。长方体要覆盖这个切片必须延伸到 zr 及以后所以 c.z2 zr 是允许的。如果写成严格大于正好 z2 等于某个 zr 的长方体会漏掉导致体积偏小。5.3 用暴力程序验证小数据写这种复杂扫描线题强烈建议先写一个暴力版本直接枚举单位格子统计每个格子被多少个长方体覆盖再累加次数 3 的体积。然后写一个数据生成器生成 n 在 3 到 8、坐标范围很小的随机数据把暴力结果和扫描线程序对比。我第一次测随机数据时发现一个很隐蔽的问题当多个矩形的 x 事件坐标相同时面积累加宽度必须放在 update 之前否则同一个 x 点会多算一段零宽度或者两个事件之间宽度算错。按这个思路检查很快就能定位。5.4 常见问题速查表症状可能原因处理方法样例输出不对pushUp 中 len2、len3 合并逻辑写错代入一个三层覆盖的具体例子手动推一遍小数据对大数据错z 区间条件等号漏写或 y 区间下标映射错误检查 c.z2 zr检查 qr 是否直接是 lower_bound 结果答案变成负数或巨大值线段树没有初始化或多次 case 之间没清空 tree每次 calcArea 开头 memset tree超时每个 z 切片都重新收集所有 rects 并排序确认 n 最大 1000理论复杂度可行检查是否死循环T 组数据间 ys/zs 没 clear上一组数据的坐标混入当前数据每次读入前 clear5.5 给线段树“改造成 k 次覆盖”的思路做完这道题可以把 len1、len2、len3 推广成 len[1..k]。pushUp 里 cnt x 时len[t] 的取值依赖于子节点的 len[t - cnt]。因为当前节点已经保证至少覆盖 cnt 层子节点只要再提供 t - cnt 层就能凑够 t 层。这个规律在很多“覆盖 k 次面积”类题目里都通用理解一次能省下以后的不少功夫。我个人做这题最大的收获不是背会了一个模板而是想明白了为什么 z 方向可以贪心地离散化枚举。很多三维计算几何题看着唬人实际上只要抓住“轴对齐 坐标离散”这两个条件就能用降维思路把体积问题变成若干个二维问题。以后再遇到类似的覆盖 N 次求并体积的题我基本都会先考虑在某一维枚举区间再用熟悉的二维扫描线去处理剩余两维。