自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:52:12，当前版本为作者最后更新于2023-11-05 21:50:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

以下内容转载自官方题解：

枚举平行于 $y$ 轴和 $z$ 轴的平面（下称平面 $x$）的位置。和平面 $x$ 有交的矩形就不用考虑了，和它无交的矩形就必须和平面 $y$ 和平面 $z$ 之一有交。平面 $x$ 在移动的过程中，即平面 $x$ 的 $x$ 坐标在从 $-\infty$ 变化到 $\infty$ 的过程中，每个矩形和平面 $x$ 有交的时间是连续的一段。在这段时间外，这个矩形必须和平面 $y$ 或平面 $z$ 有交，即 $y_{\min} \leq y\leq y_{\max}$ 或 $z_{\min}\leq z\leq z_{\max}$，其中 $y_{\min}$ 为矩形 $y$ 坐标最小值，$y_{\max}$ 为矩形 $y$ 坐标最大值，$z_{\min}$ 和 $z_{\max}$ 类似，$y$ 为平面 $y$ 的 $y$ 坐标，$z$ 为平面 $z$ 的 $z$ 坐标。画在 $x$ 平面上，就是 $y$ 平面在 $x$ 平面上的投影（一条平行于 $y$ 轴的直线）和 $z$ 平面在 $x$ 平面上的投影（一条平行于 $z$ 轴的直线）的交必须在以矩形为中心的红十字形状内。也就是二维版的本问题。

在二维版的本问题中，要判断的其实是每个矩形对应的红十字形状的交是否为空。我们取红十字形状的补集，即左上，右下，左下，右上 $4$ 个不封闭矩形区域。所有矩形的左上区域的并构成了左上的一条轮廓线，其它 $3$ 个角类似，这 $4$ 条轮廓线外的区域即为所有红十字形状的交。如果要判断交是否为空，可以先将 $y$ 和 $z$ 坐标的范围限制为 $[-M,M]$（$M$ 为本题坐标范围），为每个 $y$ 坐标计算该 $y$ 坐标上（上=on， 不是 above）有多少 $z$ 坐标位于轮廓线外。对于一个 $y$ 坐标，在这个 $y$ 坐标上的 $z$坐标其实有两个下界和两个上界，分别由左上左下右上右下轮廓提供，下界取较大的生效，上界取较小的生效。

在三维版本的问题中，我们要维护上述 $4$ 条轮廓线，同时维护每个 $y$ 坐标上有多少 $z$ 坐标位于轮廓线外。我们将所有 $y$ 坐标按照 $z$ 坐标的下界和上界由谁提供分为 $4$ 类（下界可能由左上或者左下轮廓提供，上界则由右上或者右下轮廓提供）。每一类用一棵线段树维护上下界的差。为了方便每一类的线段树都包含每个 $y$ 坐标。线段树支持查询是否有大于 $0$ 的元素。当轮廓线修改时，每段修改可用线段树区间加操作实现（等下会讲有多少修改）。由于轮廓线都是单调的，肯定 $y$ 坐标较大的部分由左上提供下界，较小的部分由左下提供。如果我们能维护一个轮廓线端点的 set，则可以在 set 上二分出左上和左下轮廓相交的位置。右侧类似。这样我们就得到了每一类的 $y$ 坐标区间。在区间上，在对应类别的线段树里查询是否有非 $0$ 位置即可。

最后是轮廓线端点的 set 维护。一个点在轮廓线上出现或消失的事件只能有常数个：它自己的长方体被平面 $x$ 扫过的开始和结束是两个事件。它可能被别的轮廓线端点挡住，仅在挡住它的轮廓线端点消失时能露出来。所有挡住它的轮廓线都消失的 $y$ 坐标的集合是一个区间（因为每个轮廓线端点消失的时间都是个区间，取这些区间的交），这个区间也只能生成 $2$ 个事件。所以一个点在轮廓线上出现或消失的事件只能有常数个。我们只要把这些事件处理出来，到对应的时间在 set 中加入或删除对应端点即可。加入和删除的时候要更新 $4$ 棵线段树。