Description

有(n)头奶牛，奶牛们的叫声很大，第(i)头和第(j)头奶牛交流，会发出(max{Vi, Vj}×|Xi − Xj |)的音量。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

Solution

看到有(max)，就想到先把奶牛按(v_i)排序。

不难发现，对于每个新加入的奶牛，它所产生的贡献为(sum{x_j}(x_j>x_i)-sum{x_j(x_j<x_i)}+v_i*(k1-k2))（(k1,k2)表示(x_i)之前有几个(x_j)，和(x_i)之后有几个(x_j)）

所以维护两个树状数组即可。记得开(long long)