本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-20 21:15:05

:::::info[闲话] 尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。尅爱死塞地刚怎么这么强。 ::::: :::::info[题目基本信息] 考察：STL，整体转移（省选/NOI-）。
题目简介：
有 $n$ 条直线和 $m$ 个桥，第 $i$ 个桥连接了 $(t_i,d_i)$ 和 $(t_i\bmod n+1,d_i)$，初始时你在 $(k,0)$，你可以不花费任何代价地向右行走任意实数长度，直到你的位置是一座桥的端点，这时你必须沿着桥走到另一端，但是在一开始的时候你可以花费 $1$ 的代价任意钦定 $t$ 和 $d$ 建一座桥（$t\in[1,n]$，同时 $d$ 可为任意实数），问最终抵达 $(s,+\infty)$ 最小代价，你需要对于每一个 $k$ 满足 $k\in[1,n]$ 求解答案。
数据范围：

• $3\le n\le 2\times 10^5$
• $1\le s\le n$
• $0\le m\le 5\times 10^5$
• $\forall i\in[1,m],1\le d_i\le 10^9,1\le t_i\le n$
• $\forall i,j\in[1,m],i\ne j,d_i\ne d_j$ ::::: 首先 $n$ 个起点 $1$ 个终点看起来就很怪，我们把移动的过程倒过来变成 $1$ 个起点 $n$ 个终点看起来就很对了。
  存在 $\Theta(nm)$ 的 01bfs 的暴力做法，但是对正解没有启发性，但是存在有启发性的 DP 做法。
  将桥按 $d_i$ 降序排序，设 $f_{i,j}$ 为考虑完前 $i$ 个桥后位置 $j$ 的答案，初始时 $\forall i\in[1,n],f_{0,i}=\min(|s-i|,n-|s-i|)$，考虑如何转移。
  看图（为方便画图我们断环为链的画）：
  
  这时我们要在 $G$ 点和 $H$ 点间建一座桥，首先先交换这两点的答案，然后：
  注意到 $H$ 点和 $I$ 点间差距大于等于 $2$ 了，我们可以从 $I$ 点建桥到达 $H$ 点，这样答案会更小，那么我们就有了思路：
• 先交换两个建桥位置的答案。
• 再对这个序列更新减小答案，具体地，找到这个序列最小值然后向两侧更新，不断递归这个过程即可。

复杂度不重要，重要的是思想。
注意到两个相邻的数之间只能相差 $-1,0$ 或 $1$，但是然后怎么办？
然后我们看刚刚的那两步：

• 交换建桥位置的答案，这个容易直接跑，接下来会产生相差的值不为 $-1,0,1$ 的相邻数对，怎么办？
• 我们不妨以交换的位置的差分类讨论，当两数相等时交换没有影响，现在只剩后面的数比前面的数大 $1$ 或小 $1$ 的情况，这两种情况类似，可以互相轴对称得出，不妨以后面的数比前面的数大 $1$ 讨论。
  如图，黑线是原来的答案构成的序列，红线是交换 $B$ 点和 $C$ 点后的答案序列，后面这一段被连续的拉下来一段（因为一直存在相差值超过 $1$ 的相邻数对，直到 $H$ 点）注意到中间这一段相邻数对前后都相差 $1$，所以我们可以考虑维护差分序列，同时维护序列中不为 $1$ 的位置序列，这个可以使用 set 维护，更新差分序列时同时更新 set 即可。
  至于细节处理仔细分讨一下也能推出（但是一坨），需要根据建桥的两个位置以及后方第一个不是 $1$ 的位置（或前方第一个不是 $-1$ 的位置）分类讨论，讨论不清楚的话细节见代码。

这样我们就做完了这道题。

时间复杂度为 $\Theta(n+m\log n)$，空间复杂度为 $\Theta(n+m)$。

code