题解

思路

把移动方案化为边覆盖

任意最终方案对应一个没有不动点的排列。对链上任意一条边，跨过它向左移动的芯片数必等于向右移动的芯片数，因此这条边对总代价的贡献一定是其边权的偶数倍。

考虑排列中每个环所覆盖的最小连续区间。沿该区间的每条边至少要各向两个方向跨越一次；反过来，对若干条边组成的集合，只要链上每个顶点都至少与一条被选边相邻，就能把每个被选边连通块中的顶点循环移动，总代价恰为被选边权和的两倍。

所以问题等价于：在链的 $n-1$ 条边中选择一个最小权边覆盖，使每个顶点至少与一条被选边相邻。答案为所选边权和的两倍。特别地，第一条和最后一条边必须被选，且不能出现两条相邻边都未选。

做法

三个算法层级

子任务 1：枚举边集

修改后枚举全部 $2^{n-1}$ 个边集，检查首尾边是否选中、是否存在相邻未选边，取合法集合的最小权值和。复杂度 $O(qn2^n)$。

子任务 2：每次线性动态规划

令 $dp_i(0/1)$ 为处理到第 $i$ 条边，且第 $i$ 条边不选或选择时的最小权值和。第一条边必须选择：

转移为

最后一条边也必须选择，答案为 $2dp_{n-1}(1)$。每次修改后重算，复杂度 $O(nq)$。

子任务 3：线段树维护边界状态

对任意连续边段维护 $f_{xy}$：在段内不存在相邻未选边、并且左右端边的选择状态分别为 $x,y$ 时，段内所选边的最小权值和。

单条权值为 $w$ 的边只有

两个有限状态。合并左右两段时枚举左段右端状态 $j$ 和右段左端状态 $k$；若 $j=k=0$，中间顶点未被覆盖，不能合并，否则更新

根节点的 $f_{11}$ 强制首尾边均被选，故每次答案为 $2f_{11}$。单点修改和查询根状态均为 $O(\log n)$，总复杂度 $O((n+q)\log n)$，空间复杂度 $O(n)$。

所有代价必须使用 64 位整数。

复杂度

三个子任务算法的时间复杂度分别为 $O(qn2^n)$、$O(nq)$ 和 $O((n+q)\log n)$；满分算法空间复杂度为 $O(n)$。