算是对这篇博客的补充吧。
设 \(a_1 \le a_2 \le \cdots \le a_n\)。
发现最优操作中一定是对相邻的数进行操作，因为如果 \(a_j\) 想把 \(x\) 给 \(a_i\)（\(i < j\)），最优是依次操作 \((j-1,j,x),(j-2,j-1,x),...,(i,i+1,x)\)。这样 \(x\) 就能造成 \((j-i)x\) 的得分。
最后全部数一定会无限趋近于 \(\bar{a}\)。考虑所有用到 \((i-1,i)\) 的操作的得分（拆贡献）。\(i \sim n\) 的数如果想把一些量给 \(1 \sim i-1\)，就必须要用到 \((i-1,i)\)。那么贡献为：
什么意思呢？如果 \(a_i < \bar{a}\)，意味着 \(\sum\limits_{j=1}^{i-1} \bar{a} - a_j > 0\)，它们想要变成 \(\bar{a}\) 必须要跟 \(i\) 右边的大于平均值的数操作，所以贡献是 \(\sum\limits_{j=1}^{i-1} \bar{a} - a_j = \sum\limits_{j=i}^n a_j - \bar{a}\)；否则 \(\sum\limits_{j=i}^n a_j - \bar{a} > 0\)，它们想要变成 \(\bar{a}\) 必须要跟 \(i\) 左边的小于平均值的数换，所以贡献是 \(\sum\limits_{j=i}^n a_j - \bar{a}\)。
这样我们得到了最终的答案：
右项容易维护，问题变成了维护左项即 \(\sum\limits_{i=1}^n i \times a_i\)。注意因为前面的讨论假定 \(a_1 \le a_2 \le \cdots \le a_n\)，所以这里的 \(i\) 实际上是排名（为了保证排名不重复需要强制重复的数按位置排序），所以单点修改相当于是加入/删除一个数。而加入/删除一个数又会让比他大的数的排名 \(+1/-1\)。
拓展一下，可以看成是维护 \(\sum\limits_{i=1}^n x_iy_i\)，每次区间加 \(x_i\) 或 \(y_i\)。这个可以用线段树做，每个结点维护 \(\sum x_i, \sum y_i, \sum x_i y_i\) 即可。时间复杂度 \(O((n + q) \log (n + q))\)。
- Operations Infinite AtCoder Regular Contestoperations infinite atcoder regular atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest builder atcoder regular contest 164 subsegments atcoder regular contest