题面

Farmer John 的 $N$ 头奶牛要过一种叫做 “哞哞节” 的节日（浓浓的 USACO 乡村风格 23333）。为了庆祝该节日，所有奶牛都要站在一条直线上并哞哞叫。

站在直线上的每头奶牛 $i$ 有一个坐标值 $x(i)$ ，且一个坐标上只能站一头牛。每头奶牛 $i$ 的听力值为 $v(i)$ 。如果奶牛 $i$ 和 奶牛 $j$ 之间要进行交流，那么这对奶牛叫声的大小等于 $max\{v(i), v(j)\}$ 乘上她们之间的距离 $|x(i) - x(j)|$ 。

请求出所有 $\mathcal{C}^{2}_{N}$ 对奶牛发出的声音大小之和。

数据范围：

$1 \le N \le 2 \times 10^4$

题目链接

分析

暴力？

我们很容易想出复杂度为 $\mathcal{O}(N^2)$ 的暴力解法。

首先我们对所有奶牛按照 $v(i)$ 升序排序。其次，对于每一头奶牛 $i$ ，我们将她分别与听力值小于她的奶牛配对。这样做的原因是，当奶牛 $i$ 与前面所有听力不如她的奶牛交谈时听力值都取 $v(i)$ ，这样也就简化了问题。配对之后我们将她们间交流的声音大小算出来，最终加在一起就是答案了。

不过看看这个题的数据范围就知道暴力肯定要 TLE。但是话又说回来，对于很多题目正解也正是基于暴力之上优化来的，我们不妨观察一下暴力解法中有何处需要优化。

我们不难发现，为每头奶牛 $i$ 配对时其所有配对的声音大小之和即 $v(i) ^{i - 1}_{j = 1} x(j) $，而后面的求和部分实际上比较类似于计算前缀和。自然地，我们想到使用树状数组对其过程优化。

树状数组优化

但是树状数组优化显得并不那么容易，因为计算差值的时候需要取绝对值，故如果我们直接用前面的坐标之和减去当前坐标乘以前面坐标数量计算得到的结果显然是错误的。

为了解决这个问题，我们不妨把听力不如奶牛 $i$ 的前 $i - 1$ 头奶牛分为两个部分：$x(j) < x(i)$ 的 $\text{left}$ 组和 $x(j) > x(i)$ 的 $\text{right}$ 组。我们记 $\text{left}$ 组奶牛的头数为 $\text{leftNum}$ ，坐标之和为 $\text{leftCordSum}$ 。同时我们记前 $i - 1$ 头奶牛的坐标之和为 $\text{cordSum}$ 。显然， $\text{right}$ 组奶牛的头数为 $\text{rightNum} = i - 1 - \text{leftNum}$ ，坐标之和为 $\text{rightCordSum} = \text{cordSum} - \text{leftCordSum}$ 。

很显然，对于奶牛 $i$ ，其与 $\text{left}$ 组里所有奶牛配对的叫声之和为 $(\text{leftNum} \cdot x(i) - \text{leftCordSum}) \cdot v(i)$ ；其与 $\text{right}$ 组里所有奶牛配对的叫声之和 $(\text{rightCordSum} - \text{rightNum} \cdot x(i)) \cdot v(i)$ 。两者之和即为奶牛 $i$ 所在所有配对的叫声之和。

很显然，我们需要维护两个树状数组：$\text{leftNumBit}$ 记录奶牛 $i$ 前 $\text{left}$ 组奶牛的数量，而 $\text{leftCordSumBit}$ 记录奶牛 $i$ 前 $\text{left}$ 组奶牛的坐标值之和 $\text{leftCordSum}$ 。

这样一来，算法复杂度就降至 $\mathcal{O}(NlogN)$ 了。

实现

完整参考代码