题解

思路

记原价值为 $S=\sum iA_i$，前缀和为 $P_i=\sum_{j=1}^i A_j$。

把第 $i$ 个元素向右移动到 $j\ge i$ 时，收益为

$$(j-i)A_i-(P_j-P_i) =\bigl(jA_i-P_j\bigr)+P_i-iA_i.$$

对固定 $i$，需要在所有 $j\ge i$ 中最大化直线 $y=jx-P_j$ 在 $x=A_i$ 处的值。

向左移动到 $j\le i$ 时，收益为

$$(j-i)A_i+(P_{i-1}-P_{j-1}) =\bigl(jA_i-P_{j-1}\bigr)+P_{i-1}-iA_i.$$

这同样是动态加入直线并查询最大值。分别从左向右、从右向左扫描，用李超线段树维护直线即可。

做法

子任务 1：直接模拟移动

枚举原位置和目标位置，实际删除、插入并重新计算序列价值。复杂度为 $O(n^3)$。

子任务 2：枚举位置对

预处理前缀和，枚举 $(i,j)$ 后用上面的公式在 $O(1)$ 时间计算收益。复杂度为 $O(n^2)$。

子任务 3：动态凸包

两次扫描分别处理向左、向右移动。每次加入一条斜率为位置、截距由前缀和决定的直线，并在 $A_i\in[-10^6,10^6]$ 处查询最大值。李超线段树每次插入和查询均为 $O(\log 2\times10^6)$。

正确性证明

引理 1

向右移动 $A_i$ 到 $j$ 的收益为 $(j-i)A_i-(P_j-P_i)$。

证明。 $A_i$ 的系数增加 $j-i$；原区间 $i+1,\ldots,j$ 中每个元素的系数减一，损失为其元素和 $P_j-P_i$。$\square$

引理 2

向左移动 $A_i$ 到 $j$ 的收益为 $(j-i)A_i+P_{i-1}-P_{j-1}$。

证明。 $A_i$ 的系数变化为 $j-i$；原区间 $j,\ldots,i-1$ 中每个元素的系数增加一，贡献为该区间元素和。$\square$

引理 3

两棵动态直线结构返回每个 $i$ 向左和向右移动的最大收益。

证明。 由引理 1、2，所有与目标位置有关的部分均可写成 $mA_i+b$。扫描到 $i$ 时，结构中恰含对应方向全部合法目标位置的直线，因此最大值查询恰好枚举了所有合法移动。$\square$

定理

算法输出一次移动后的最大序列价值。

证明。 任意操作要么向左移动、向右移动，要么插回原位。由引理 3，算法取到前两类操作的最优收益，并与零收益比较；加上原价值后即为全局最优答案。$\square$

复杂度

时间复杂度为 $O(n\log 2\times10^6)$，空间复杂度为 $O(2\times10^6+n)$。