Yet Another Many Moves Problem.

写了个垃圾做法，看来我对 Many Moves 的理解还不够深刻。

从小往大扫时间。这个问题没有后效性，考虑 dp。

记 $y_{i,j}$ 表示时刻 $i$ 的第 $j$ 个音符所在位置，其中 $j\in \{1, 2\}$。注意到在第 $i$ 个时刻，为了完成要求，一定有一只手会移动到 $y_{i,1}$ 这个位置，并且为了保证花费最小，在当前时刻一定不会再移动这只手。所以设 $f_{i,j}$ 表示在第 $i$ 个时刻，从初始状态依次完成前 $i$ 个要求，最后两只手分别位于 $y_{i,1}$ 和 $j$ 的最小花费。那么答案就是 $\min\limits_{j=1}^nf_{m,j}$。

记 $\operatorname{dis}(i,j)$ 为 $i,j$ 两点的环上距离，显然 $\operatorname{dis}(i,j)=\min\{|i-j|,n-|i-j|\}$。

考虑转移。枚举 $i-1$ 时刻另一只手在哪个位置，记为 $k$。

若 $i$ 时刻只有一个音符，那么考虑两只手分别怎么移动，有：

注意到 $f_{i,j}+\operatorname{dis}(j,k)\ge f_{i,k}$。因为 $f_{i,j}$ 表示从初始状态开始依次完成前 $i$ 个要求后，最终两只手位于 $y_{i,1}$ 和 $j$。加上 $\operatorname{dis}(j,k)$ 后就是再从 $j$ 走到 $k$，相当于完成了一个这样的过程：从初始状态开始依次完成前 $i$ 个要求，最终两只手位于 $y_{i,1}$ 和 $k$。而 $f_{i,k}$ 表示该过程的最小花费，所以上式自然成立。

那么转移方程可以改写成：

若 $i$ 时刻有两个音符，仍可用上式求出 $f_{i,y_{i,2}}$。其他的位置不能这样求因为不能保证转移的过程中经过了 $y_{i,2}$。

注意我们状态的定义，其应当满足这个状态完成了前 $i$ 个要求。所以对于剩余位置 $j$，$f_{i,j}$ 对应的移动方案一定可以划分为两个部分：先完成前 $i$ 个要求且两只手恰好在 $y_{i,1}$ 和 $y_{i,2}$，再 $y_{i,2}$ 那只手移动到 $j$。所以有：$f_{i,j}=f_{i,y_{i,2}}+\operatorname{dis}(y_{i,2},j)$。

扫描 $i$ 的过程中用一个数据结构维护当前的所有 $f_j$。转移都是区间操作的形式，考虑使用线段树维护。

将环上距离拆开可以发现，我们要支持的其实是以下几种操作：

每个位置维护一个三列的矩阵，则上述操作可以轻松使用 $(\min,+)$ 矩阵乘法实现。不过可以注意到只有三个位置是有用的，因此可以只记录那三个位置的信息，这样常数小一点。

认为 $n,m$ 同阶，时间复杂度 $\mathcal{O}(m\log n)$，空间复杂度 $\mathcal{O}(n)$。