自动搬运

查看原文

来自洛谷，原作者为

	SDLTF_凌亭风 人生的相遇相逢不存在 O(1)，愿每位 OIer 仍在路上

搬运于2025-08-24 22:20:11，当前版本为作者最后更新于2023-08-28 13:17:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题可以看做是 IOI2001 Mobile Phones 的升级版。那么这个题解来说说怎么把他降级回去。

请注意，题目说的虽然给出的是长方体，而你要关注的是矩形。

第一个问题就是，在三维的空间中，怎么构出一个矩形？

按照题目的输入格式，一个长方体被表示为 $(x_1, y_1, z_1, x_2, y_2, z_2)$ 。不难想到，当 $x_1=x_2$ 或 $y_1=y_2$ 或 $z_1 =z_2$ 时，长方体退化为矩形。

我们记上面三种情况分别为 A 类长方体、B 类长方体和 C 类长方体。

接下来考虑如何统计答案。记 $f(A,B)$ 表示：对于所有 A 类长方体和 B 类长方体，统计有多少对满足如下两个条件：

1. 有一个长方体是 A 类；
2. 两个长方体有公共点。

那么最终的答案可以转化为 $f(A,B)+f(B,C)+f(A,C)$。

接下来，讨论如何计算 $f(A,B)$，剩下两项同理。

想像有一根扫描线，沿着 $y$ 轴移动，观察空间中由 $x$ 轴和 $z$ 轴构成的平面（简单地说，把这个长方体投影一下）。显然的，A 类长方体变成了一条垂直线段，而 B 类长方体是个矩形。

并且，在扫描线移动的过程中，A 类长方体会被扫过一段时间，而 B 类长方体只会在某一个时间点被扫过，理由是 B 类长方体满足 $y_1=y_2$。

显然，扫描线的移动会导致以下三种事件的发生：

1. 遇到了新的 A 类长方体的起点；
2. 遇到了 B 类长方体的起点，并且立即遇到其终点；
3. 遇到了旧的 A 类长方体的终点。

既然你把一个三维的空间搞成了二维平面，接下来要干的事情，就和 IOI2001 Mobile Phones 一样了。

如果你使用二位树状数组来维护，那么总体时间复杂度就是 $O(n \log n + n \log m)$ 的，其中 $m$ 为所给出所有的长方体所有的坐标中的最大值。

具体的代码实现建议参考官方题解。