P7624 [AHOI2021初中组] 地铁 题解

挺好玩的这题其实

首先容易观察到答案是一段连续的区间。因此对于答案区间 $[l,r]$，考虑二分求解。这样的问题有两种策略：

• 先找到一个合法位置，然后以这个位置为分界线向左向右分别二分。
• 直接分别二分出区间左右端点。

这里采取第二种做法。

判断当前二分到的总长度 $x$ 是否合法是简单的，直接差分约束做即可。但是问题是若当前不合法，则无法知道合法区间是在 $x$ 的左侧还是在 $x$ 的右侧，这里考虑使用一些巧妙的手法：

对于建边关系而言：

• 对于 $1$ 操作：
  • 若有 $a<b$，则其距离起点 $1$ 的数组 $x$ 的关系形如 $x_b-x_a\ge c$，转化成基本模型是 $x_a-x_b\le -c$，该边边长和二分到的 $x$ 没有任何关系。
  • 若有 $a>b$，则其 $x$ 值的关系形如 $x_b-x_a+x\ge c$，转化成基本模型即 $x_b-x_a\ge c-x$，$x_a-x_b\le x-c$，该边的边长和 $x$ 成一倍增加关系。
• 对于 $2$ 操作：
  • 若有 $a<b$，则其距离起点 $1$ 的数组 $x$ 的关系形如 $x_b-x_a\le c$，该边边长和二分到的 $x$ 没有任何关系。
  • 若有 $a>b$，则其距离起点 $1$ 的数组 $x$ 的关系形如 $x_b-x_a+x\le c$ 即 $x_b-x_a\le c-x$，该边边长和 $x$ 成负一倍增加关系。

然后还有相邻两个元素之间的关系，对于 $i=1\ldots n-1$，其形如 $x_i+1\le x_{i+1}$，容易发现该边边长和二分到的 $x$ 没有任何关系。而对于 $i=n$ 的特殊情况，此时有 $x_n\le x_1+x-1$ 即 $x_n-x_1\le x-1$，此时该边边长和 $x$ 成一倍增加关系。

于是考虑在差分约束建边的时候，额外增加一个信息表示其和二分到的值 $x$ 之间的关系，该关系的值一定是 $-1,0,1$ 中的一个。然后若总长度为 $x$ 是不合法的，则考虑找出其所在的负环（这个可以在 spfa 的过程中通过记录路径得到），容易证明若其负环上所有倍率边的和为 $0$，则此时不管怎么调整 $x$ 的值都必然会存在负环，即必然无解。否则，若该值 $>0$，则通过把 $x$ 的值往大调整就可以使得该负环上边权值的和增大直到其权值之和为正。

该值 $<0$ 的情况同理，此时把 $x$ 的值往小调整即可。

总时间复杂度为 $O(nm\log V)$，可以通过该题。