洛谷 P4125 题解

璀璨星空1 · 2021-08-21 22:26:13 · 题解

考虑先做第二问，再做第一问.

我们想要构造一种 n 轮均合法的移动操作，将 n 片针叶全部都移走；考虑先移走 1 片，将问题转化为 n-1 片针叶全部都移走，不难发现这是我们必须解决的，而且这样问题只会变简单.

哪 1 片针叶是可以立刻就移走的？比如说我们想要让这片针叶向下直接移走，那么这片针叶下面就不能有任何的阻碍，一个粗糙的想法是直接选择 y 坐标最靠下的那片针叶.

但是这样可能会出问题，如下图所示：

如果我们直接向下移动红色的针叶，会被蓝色的针叶所阻碍.

这启发我们，找到一片没有被任何针叶阻碍的针叶，还是以向下移走为例子，我们看，如果只考虑上下之间的障碍，能否一定能够找到一片，没有被任何针叶阻碍的针叶.

首先，如果针叶 u 阻碍了针叶 v，那么不可能反过来，也就是不可能针叶 v 能够阻碍针叶 u.

因此，如果对于每个针叶 i，都看成一张图上的一个结点 i，那么这张图就是一张有向无环图.

比如说对于我们的第一个样例而言，针叶建点，阻碍关系建边，就是这样一张图：

知道了有向无环图有什么用呢？任意一张有向无环图上，一定存在一个结点，没有任何入度.

反证法，如果所有结点都有入度，反图上所有结点就都有出度，此时我们任意选一个点不断走下去，瞎走一通，走到 n+1 步，就一定能找到一个环，这样原图上也就一定能找到一个环.

这样，我们一定能够找到一片针叶 t，可以向下直接移走 t；重复上述过程 n 步，就说明了一定存在一组合法的解，使得所有的针叶最终都是向下移动的.

这启示我们，如果能够把这张有向无环图真正建出来，它的拓扑序的逆序列就是一个合法的移动序列，按照这个移动序列，一片一片向下移动针叶即可.

直接建图需要枚举 \mathcal{O}(n^2) 条边，不能接受，考虑挖掘为了求出这个图的拓扑序，有什么好的性质.

注意到，如果针叶 u 阻碍了针叶 x，针叶 x 又阻碍了针叶 y，那么可以直接看作针叶 u 阻碍了针叶 y，即使这样的阻碍关系实际上并不存在，

只知道这个性质是没有什么用的，我们并不能刻画出一片针叶 u “恰好” 被哪片针叶所阻碍，又能够 “恰好” 阻碍到哪片针叶.

考虑换一种方式刻画阻碍关系，不再思考点对点贡献，而是直接思考，某个给定的 x 坐标那条直线上，一条平行于 y 轴的直线，会产生什么样的阻碍关系.

假如不考虑边界情况，所有与这条直线有交点的针叶，两两之间都存在阻碍关系.

建图的时候，只要在相邻两片针叶之间，建一条边即可.

如果我们把这条直线稍稍向右移动一些，你可以认为移动了 \varepsilon 的距离，还是不考虑边界情况，没有到达或者跨过整点，那么能建的边和刚才那条直线是完全一样的.

如果移动很多呢？即使跨过了很多整点，只要与这条直线有交点的针叶集合没有变化，能建的边就都不会有变化，回归点对点贡献的思考.

对于两片针叶 u 和 v，因为初始状态下两片针叶是无交点的，所以选哪条直线去截它们，能不能连边，连边的方向是什么，只要都截上了，就不会有任何区别.

也就是说，对于某个集合的针叶来说，对于所有能够把它们全截下来的，与 y 轴平行的直线，针叶之间内部连边的序不会有任何变化，哪片针叶在上面就永远会在上面，哪片在下面就永远会在下面.

用一条与 y 轴平行的扫描线，扫过整个平面，x 坐标从 -\infty 扫到 +\infty.

假设我们已经处理完了 x\leq x' 的时候，所有直线能建的边，考虑处理 x=x'+1.

• 可能会新来一片针叶
  • 需要确定在这片针叶上面的针叶中最靠下的，也就是前驱；再确定在这片针叶上面的针叶中最靠下的，也就是后继，那么新来的针叶阻碍了前驱，后继阻碍了新来的针叶.
  • 用一个 \texttt{STL Set}，可以维护所有，与目前扫描线有交点的针叶的编号，新来一片针叶，先在 \texttt{Set} 中查询前驱、后继，之后在 \texttt{Set} 中加入这片针叶即可.
• 可能会有一片针叶消失了
  • 并不需要做什么事情，只要在 \texttt{Set} 中删除这片针叶即可.

如果这样处理，可能会面临一些小问题：

• 如何重定义 \texttt{Set} 的小于号，使得我们可以在不断改变的 x 坐标下比较两条线段的 y 坐标？
  • 利用序不改变的性质，我们可以 ”欺骗“ \texttt{STL}：虽然我们传进去的小于号不是严格全序，但是在 \texttt{STL} 的运作周期内，永远都不会发现这一点.
  • 将每条直线用斜截式 y=kx+b 表示，那么 k 和 b 是直线的参数，x 是递增的，y 是需要比较的关键字，之后我们重定义小于号，从某个全局参数处读取此时的 x 进行比较.
  • 这就是说，在扫描线的过程中，每扫到一个有变化的 x 坐标，就微调一下小于号的规则.
  • 因为前面提到的序不变的性质，在 \texttt{STL} 的运作周期内，不可能发现该小于号不是严格全序.
• 如果同一条直线上，又有插入又有删除，该怎么处理？
  • 不难发现，此时要插入的直线和要删除的直线之间，实际上是不能连边的.
  • 对同一个 x 坐标对应的截线，只要一律先处理删除，再处理插入即可.
• 如此，对于每片针叶，我们会在刚扫到这片针叶的时候，让这片针叶连入、连出各不超过 1 条边，这样我们就建出来了，实际阻碍关系图的一张等效图，图上有 n 个结点和不超过 2n 条有向边.

以上是考虑从上到下的阻碍关系建出来的图，我们对这张图作拓扑排序，令针叶 i 在这张图上的拓扑序为 \alpha_i，同理，考虑从左到右的阻碍关系，令针叶 i 在那张图上的拓扑序为 \beta_i.

对于第一个样例而言，一组可能的 \alpha 和 \beta 分别是 \{1,4,2,5,3\} 和 \{1,4,2,3,5\}.

按照拓扑序，将所有针叶向上移动，或者向右移动，可以正确回答所有数据点的第二问，时间复杂度为 \mathcal{O}(n\log n)，在第一问上随便输出一个 1，就可以获得 60 分的好成绩.

这里要特别注意，实际考试如果遇到这样分步给分的题目，对不想回答的小问，一定要注意什么样的输出是不给分但是可以被接受的；在这道题中，如果第一问随意地输出了 0，就会导致第二问的分白白丢掉.

在验证了 \alpha 和 \beta 的正确性之后，就可以考虑如何利用刚才的性质和结论，解决第一问了.

考虑如何判定一步给定的移动操作是不是合法的，这次以向上直接移动为例子.

将一片 x 坐标范围为 [l,r] 的针叶向上移动，假设这片针叶是 u，什么样的针叶 v 会对 u 造成阻碍呢？

注意到我们直接在刚才建出来的图上找是不可行的，有这样的一些原因：

• 可能有些针叶 x 能对 u 造成阻碍，但是我们把 x 移走了；
• 如果要处理移走了的针叶，仅仅靠一张等效图是不够的，而原图又没有办法建出来.

这里最大的问题，是我们要试图删除一片针叶，这会破坏这张等效图的等效性.

正难则反，删除操作不可行的时候，考虑逆转时间轴，时间倒流，考虑插入操作.

也就是说，我们从已经被移空了的平面开始，按照操作顺序的倒序，一片一片加入针叶，加入的过程就是从无穷远处移动回原来所在的地方，看哪些针叶会在这个加入的过程中被阻碍.

注意到如果这样做，是不可以剪枝的，必须考虑每一片针叶，因为有可能后来的针叶被阻碍了，前面的针叶也被阻碍，这也就意味着无论一片针叶有没有被阻碍，我们都要在平面上将这片针叶安排回原来的位置，因为这片针叶还有可能去阻碍别人，如果考虑逆转时间轴的实际意义，很容易说明这一点.

既然单从图论的角度难以直接解决问题，我们还是回归移动针叶被阻碍这件事的实际意义.

一片针叶 v 会对 u 造成阻碍，说明 v 的 x 坐标范围 [l',r'] 与 [l,r] 是有交的，这里我们将 v 分为两种针叶，分别称作 \texttt{P} 类针叶和 \texttt{Q} 类针叶：

考虑这些针叶，如何判断这些针叶到底会不会对 u 造成阻碍？这时就要看这些针叶的 y 坐标了，然后我们陷入了和一开始做第二问的时候同样的困境：怎么直接地求出两片针叶之间的阻碍关系呢？

注意到这里考虑到的所有针叶对 (u,v)，它们之间一定是存在阻碍关系的，要紧的只是关系的方向，需要知道存不存在 v 阻碍 u 的关系.

既然一定存在阻碍关系，那其实就好办了，还是回归那张等效图.

这时解法基本上已经呼之欲出了，我们不是求出了等效图拓扑序 \alpha 吗，那对于我们已经知道确实存在阻碍关系的针叶对 (u,v)，如果 \alpha_u<\alpha_v，那就是 u 阻碍 v，否则就是 v 阻碍 u 啊.

可能会产生一个疑问：如果直接当作 \alpha_v 去处理的话，两片 \texttt{Q} 类针叶之间的阻碍关系是不是可能会误判呢？但其实这是不要紧的，因为我们根本不关心这些，我们只关心所有的针叶对 (u,v).

所以判断其实很简单：考虑所有坐标范围与 [l,r] 有交的针叶，如果这里面，\alpha_v 的最小值，都大于 \alpha_u 的话，那么全是 u 阻碍 v，所以这一步移动 u 的操作一定是可行的，反之，则一定不可行；

需要用数据结构快速维护这个过程，不难想到线段树，具体过程如下：

• 将所有移动操作读入进来离线，逆转时间轴，逆序考虑所有的操作；

  • 当然在这之前，要先离散化所有的坐标，注意离散化是在这一步才进行，而不是在一开始的时候就进行离散化，否则因为斜率等问题会产生错误.

• 建立两棵线段树 T_x 和 T_y；

• 设这一步移动操作移动的针叶编号是 u，u 的 x 坐标范围是 [l_x,r_x]，y 坐标范围是 [l_y,r_y]：

  • 设布尔标记 \texttt{Flag} 为真；
  • 如果是操作 \texttt{0}，也就是向左移动：
  • 在 T_y 中查询 [l_y,r_y-1] 的区间最大值，如果该值大于 \beta_u，就令 \texttt{Flag} 为假；
  • 如果是操作 \texttt{1}，也就是向上移动：
  • 在 T_x 中查询 [l_x,r_x-1] 的区间最小值，如果该值小于 \alpha_u，就令 \texttt{Flag} 为假；
  • 如果是操作 \texttt{2}，也就是向右移动：
  • 在 T_y 中查询 [l_y,r_y-1] 的区间最小值，如果该值小于 \beta_u，就令 \texttt{Flag} 为假；
  • 如果是操作 \texttt{3}，也就是向下移动：
  • 在 T_x 中查询 [l_x,r_x-1] 的区间最大值，如果该值大于 \alpha_u，就令 \texttt{Flag} 为假；
  • 在 T_x 中以 \alpha_u 的值更新区间 [l_x,r_x-1]；
  • 在 T_y 中以 \beta_u 的值更新区间 [l_y,r_y-1]；
  • 若 \texttt{Flag} 为假，记录目前的操作步骤 i 是不合法的；

最终最早的不合法步骤即为第一问的答案，可以正确回答所有数据点的第一问，时间复杂度为 \mathcal{O}(n\log n)，空间复杂度为 \mathcal{O}(n)，可以获得这道题的 100 分.

常数主要在线段树上，如果写 zkw 线段树可以降低常数，但是考虑到 3 秒的时间限制，没有必要.

肝了 3.5h，接近 300 行、7.7 个 KB 的代码不得贴一下 qwq.