ARC114D Moving Pieces on Line

题意 ：数轴上有 个球，第 个球位置为 。

初始时，数轴全为白色。可以每次选择一个球向左或者向右滚一段距离，且将滚过的部分反色。

给定 个不交的区间，要求恰将这些区间染成黑色。

求球滚过的最小总距离，或指出无解。

，时限 。

---

不难发现，在最优方案中，对于单独某个球，其滚动不可能回头，相当于只滚了一次。

区间操作不便处理，用 xor 差分转化问题。

记 为区间 ，目标状态相当于指定若干个 为黑色。

将位于 的球滚到 ，相当于给 各异或上 ，代价为 。

处的异或操作是确定的，预先计算。序列中剩余的 就是 需要放的位置。

剩下的问题就是：

数轴上有若干个红点（），若干个蓝点（剩余需要 xor 的位置），找出一个匹配（蓝点不能匹配蓝点，其余都行），使得距离和最小。

（蓝红匹配就是用 去填剩余需要 xor 的位置，红红匹配是因为红点太多，内部抵消掉一些）

---

若蓝点数大于红点数则无解（蓝红点数奇偶性不同也无解，不过题目保证没有这种情况）。先考虑蓝红点数相等的情况。

不难发现，一对交叉的匹配可以不劣地调整为一对不交叉的匹配，于是一定存在一种最优解是不交叉的。

将红蓝点分别排序，按排名对位匹配即可。

接着考虑红点多余的情况，若我们钦定了一个红点的匹配集合，必然是内部相邻的匹配，外部按排名匹配。

可以发现，若两个排名不相邻的红点匹配，可以不劣地调整成两个排名相邻的红点匹配。

记 表示前 个红点匹配了前 个蓝点的最小代价。转移有两类：

• 一蓝一红：

• 相邻两红：

复杂度 （ 同阶）。