比赛链接

给定 $n$ 条轨道和一个含有 $m$ 个音符的谱，每个音符出现的轨道为 $p_i$。

玩家有两个手指，一开始分别位于轨道 $1$ 和轨道 $n$ 的底部，且两个手指每秒可以向左右移动一格。

玩家的任务是在音符恰好到达底部时用手指敲击音符。

现要求构造每个音符到达底部的时刻，使得谱中每个音符依次出现的时刻不早于上一个音符，且玩家可以顺利完成任务。

要求最小化最后一个音符达到底部的时刻，如果有多种方案，任意输出一种即可。$(n,m\le 5000)$

设 $f(i,j)$ 表示第 $i$ 个音符到达底部且左右手位于 $(p_i,j)$ 的最小时刻，$g(i,j)$ 表示第 $i$ 个音符到达底部且左右手位于 $(j,p_i)$ 的最小时刻。

于是不难得到 $f,g$ 的状态转移，这里仅列举一种

$$ f(i,j)=\min\left(f(i-1,k)+\max(|p_i-p_{i-1}|,|j-k|),g(i-1,k)+\max(|p_i-k|,|j-p_{i-1}|)\right) $$

暴力做法时间复杂度 $O(n^2m)$，方案输出用回溯即可。

考虑两棵线段树维护序列 $\{f(i-1,k)+\max(|p_i-p_{i-1}|,|j-k|)\}$ 和 $\{g(i-1,k)+\max(|p_i-k|,|j-p_{i-1}|)\}$ 的最小值。

$j\to j+1$，不难发现对上述两个序列都可以通过分类讨论后用区间加操作维护，于是时间复杂度 $O(nm\log n)$。