A. 牛奶求和

首先对于一个排列，\(T=\sum_{i=1}^{n}a_i\times i\)。由于 \(i\) 越大，权重越大，所以将 \(a\) 排序计算 \(T\) 一定是最优的。

现在把一次操作转化成删除一个数再加进一个数。
设旧数为 \(a\) 新数为 \(b\), \(a\) 的位置为 \(w_0\)(多个值取)，\(b\) 的位置为 \(w_1\)。设前缀和数组为 \(s\)，\(T\) 为开始产奶量。
位置可以用二分做。

考虑分类讨论。

当 \(w_1\le w0\) 时

• 删 \(a\) 减小 \(a\times w_0\)，加 \(b\) 增加 \(bw_1\)。操作前 \([w_1,w_0-1]\) 的数位置都加 \(1\)。于是再加 \(s_{w_1-1}-s_{w_0-1}\)。
• 即为 \(T-aw_0+bw_1+s_{w_0-1}-s_{w_1-1}\)。

当 \(w_0\lt w1\)

• \(a\) 一样，但加 \(b\) 时前面少了一个数，所以是 \(b(w_1-1)\), 同时 \([w_0+1,w_1-1]\) 都减 1。
• 即为 \(T-aw_0+b(w_1-1)-s_{w_1-1}+s_{w_0}\)。