CF1612G Max Sum Array 题解

容易发现原式的值即为：$\sum\limits_{i=1}^m\sum\limits_{j=1}^{c_i}(2j-c_i-1)x_{i,j}$，其中 $x_{i,j}$ 表示值为 $i$ 的第 $j$ 个数的位置，要求所有 $x_{i,j}$ 恰好不重不漏的取完 $1\sim\sum\limits_{i=1}^mc_i$ 内的所有整数。此时容易想到直接贪心，把所有位置按照对应的系数 $2j-c_i-1$ 从大到小排序然后依次对应从大到小 $\sum\limits_{i=1}^mc_i\sim 1$ 内的所有数，容易证明这个贪心策略最优。

第二问也是容易的，发现为了保证上式的值最大，肯定不会交换两个系数不同的数的 $x_{i,j}$ 的值，因此直接求出每个数都出现了几次然后把出现次数的阶乘乘起来即可。

但是直接模拟上述流程时间复杂度为 $O(\sum c_i)$（排序可以写桶排优化到 $O(n+V)$），无法通过。注意到值域很小，所以直接差分加前缀和求出每个系数的出现次数，然后在值域上双指针扫描即可将时间复杂度优化到 $O(n)$。