P9447题解

· · 题解

题意

从一个点向外射出 n 条足够长的线段形成一个环，逆时针顺序依次编号为 1\sim n，其中有 m 条边连接两个相邻线段上的两个点，满足这两个点到原点距离相等，且任意两条边到原点的距离不等。现在从原点出发，初始选择一条线段，然后一直向外走，若遇到一条边则立即沿着边走到另一侧并继续往外走，直到走到某条线段的端点。现在希望最后走到第 s 条线段的端点。你可以加入任意多条边，这些边也要满足两点到原点距离相等和任意两边距离不等的要求。对于每个 i，求出至少要加入多少条边。n\le 2\times 10^5,m\le 5\times 10^5。

思路

容易发现这个过程是可逆的，即从一个位置出发的下一步是唯一的，而从一个位置向后倒推也能唯一推出从原点到这个位置的路径是什么样子的。因此一个简单的想法是从 s 出发倒着做，则我们需要处理一个最短路状的问题。

考虑一种类似扫描线的想法，倒着扫描每条边，实时对每个 i 维护当前已经考虑过的部分中，从 s 到 i 所需增加的最少的边的数量，记为 f_i。则考察加入一条边对 f 产生的影响是什么。假设加入了 (x,y) 这条边，则在这条边上面的路径向下走的时候，x 会走到 y，y 会走到 x，因此影响是 f_x,f_y 互换。此后，我们开始加入一些边。容易发现我们加入的边一定按照先后顺序形如 (l,l+1),(l+1,l+2),\cdots,(r-1,r) 或反过来。目的是为了从 f_l 更新到 f_r。这样我们就得到了一个暴力的做法，每次暴力枚举 l,r 并更新。这样做的复杂度是 O(mn^2)。

第一个优化是显然的，由于我们上一步只修改了 f_x,f_y 的值，而在这之前我们得到的结果已经是最新的结果了，所以对于一个 i\ne x,i\ne y 的位置 i，它对其它元素的更新是无效的。因此我们只需要枚举 l=x,y 和 r 更新即可。复杂度变为 O(mn)。需要注意的是，由于我们交换 f_x,f_y 这一步操作的时候可能会使得 f_x,f_y 的值变大，所以我们还需要先用别的值更新 f_x,f_y。但此时必然是用 f_{x-1}\to f_x，f_{y+1}\to f_y，原因是若 f_{a}\to f_x 更优，则说明 f_a\to f_{x-1} 也可以被更新，但我们在上一步已经处理过这样的更新了。

下面剩余的部分就是数据结构维护这个事情。我们需要维护一个数据结构，支持区间对公差为 \pm1 的等差数列取 \min，单点修改与单点查询。使用两棵线段树分别维护公差为 1,-1 的操作。此时一次操作可以看作区间对 v+i 或 v-i 取 \min，在线段树节点上记录区间内 v 的最小值，单点查询时查询其 v 的最小值再加上或减去 i 即可得到真实的值。线段树维护的部分应当是简单的，这样就做完了，复杂度 O(m\log n)。

代码