CDQ 分治做题记录
P2345 [USACO04OPEN]MooFest G
按 (v) 从小到大排序，这样可以转化为 (v_j imes|x_i-x_j|(i<j))。
考虑如何计算前一段区间对后一段区间的贡献。设前一段当前扫到 (i)，后一段当前扫到 (j)。
如果 (x_ileq x_j)，则贡献为 (sumlimits_{k=j}^r x_k-x_i)；如果 (x_i>x_j)，则贡献为 (sumlimits_{k=i}^{mid}x_k-x_j)。
直接做比较困难，不妨将前者的贡献也挪到 (j) 向后移动时计算。具体等于 (x_j imes(i-l)-sumlimits_{k=l}^{i-1}x_k)。
预处理前一段区间总和，扫的时候记录前一段区间当前前缀和即可。