[ARC126E] Infinite Operations()

首先考虑,怎么样操作最优?
不难发现我们应当先给序列排序,每次只会修改相邻两个数,因为如果跨过一个在这两个值之间的数,那么我们显然可以将操作传递过去,保证贡献为 \(2x\) 且操作等价。
最终答案会怎么样呢?
不难发现每次操作不会影响这两个数和后面的数的差的和,那么总贡献就为

权值线段树维护即可。

————————

首先考虑,怎么样操作最优?
不难发现我们应当先给序列排序,每次只会修改相邻两个数,因为如果跨过一个在这两个值之间的数,那么我们显然可以将操作传递过去,保证贡献为 \(2x\) 且操作等价。
最终答案会怎么样呢?
不难发现每次操作不会影响这两个数和后面的数的差的和,那么总贡献就为

权值线段树维护即可。