企业官网建设流程全解析

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[i+1]，注意是左闭右开。遍历所有长方体，如果一个长方体满足：

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, i+1) 代表实际 y 区间 [ys[i], ys[i+1])，长度为 ys[i+1] - 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; } }; vector<int> ys; // y 方向离散化数组 struct SegNode { int cnt; int len1, len2, len3; } tree[MAXN << 2];

4.2 pushUp 与 update

pushUp 按上面推导的五种情况写。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(vector<Rect>& rects) { if (rects.empty()) return 0; vector<Event> 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); vector<Cube> cubes(n); vector<int> 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]; vector<Rect> 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 常见问题速查表

5.5 给线段树“改造成 k 次覆盖”的思路

做完这道题，可以把 len1、len2、len3 推广成 len[1..k]。pushUp 里 cnt == x 时，len[t] 的取值依赖于子节点的 len[t - cnt]。因为当前节点已经保证至少覆盖 cnt 层，子节点只要再提供 t - cnt 层就能凑够 t 层。这个规律在很多“覆盖 k 次面积”类题目里都通用，理解一次能省下以后的不少功夫。

我个人做这题最大的收获，不是背会了一个模板，而是想明白了为什么 z 方向可以贪心地离散化枚举。很多三维计算几何题看着唬人，实际上只要抓住“轴对齐 + 坐标离散”这两个条件，就能用降维思路把体积问题变成若干个二维问题。以后再遇到类似的覆盖 N 次求并体积的题，我基本都会先考虑在某一维枚举区间，再用熟悉的二维扫描线去处理剩余两维。