P6372 [COCI2006-2007#6] PROSTOR 题解

· · 题解

这个题可以看做是 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 为所给出所有的长方体所有的坐标中的最大值。

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