「题解」Solution P5094
Description
给定两个长度为 (n) 的序列 (v_i,x_i)，定义一个点对 ((i,j))（(i e j)）的价值 (f(i,j)) 为 (max(v_i,v_j) imes |x_i-x_j|)，求：
[sumlimits_{i=1}^n sumlimits_{j=1}^n f(i,j)[i e j] ]
Solution
很难想象这只是一个绿题，可能拿树状数组做会舒服一点吧，这里介绍分治做法。
我们把 (displaystyle sumlimits_{i=1}^n sumlimits_{j=1}^n f(i,j)[i e j]) 先拆成 (displaystyle sumlimits_{i=1}^nsumlimits_{j=1}^n max(v_i,v_j)[i e j]) 和 (displaystyle sumlimits_{i=1}^n sumlimits_{j=1}^n |x_i-x_j|[i e j])，看看分别怎么计算：
- (displaystyle sumlimits_{i=1}^nsumlimits_{j=1}^n max(v_i,v_j)[i e j]) 我们把 (v_i) 升序排列一下，那么第 (i) 个数的贡献即为前 (i-1) 个数。
- (displaystyle sumlimits_{i=1}^n sumlimits_{j=1}^n |x_i-x_j|[i e j]) 我们把 (x_i) 升序排列一下，那么定 (j) 为右端点，下面这一段就可以如下化简：
其中 (sum_i) 为前缀和。
那把这两个融合起来怎么搞呢？我们可以用结构体输入这两个序列，以 (v) 为第一关键字先把序列进行排序。
现在对于区间 ([l,r]) 计算他的贡献，这一段区间的 (v) 是已经排好序的，所以考虑分治，将区间分为两半 ([l,mid]) 和 ([mid+1,r])，可以通过递归算出贡献在 ([l,mid]) 的和贡献在 ([mid+1,r]) 的，接下来要算的就是有贡献的跨越这两个区间的。
我们在 ([mid+1,r]) 中枚举 (j) 作为贡献的右界，算 ([l,j]) 的贡献，并将其加起来作为跨区间的贡献和。将其分拆为 (v) 和 (x) 两部分计算：
- (v)，既然排过序了那么全部都是 (v_j)。
- (x)，其中 ([l,j]) 的贡献会有一个位置 (i) 使得 (i) 是最后一个 (a_i(x) le a_j(x)) 的，那么区间 ([l,j]) 的贡献就可以如下计算（(sumx_{[l,r]}) 为 (a_{[l,r]}(x)) 的和）：
通过预处理前缀和这个是可以 (mathcal O(1)) 求的，也就是对于一个 (j)，他对答案的贡献为：
但注意，能将其如上计算的前提是 ([l,mid]) 和 ([mid+1,r]) 分别按照 (x) 进行排序。
我们都知道有归并排序，所以可以处理完上面这些之后再将 ([l,r]) 以 (x) 为关键字排一下序。我们不用在处理答案前排序的原因应该很简单，因为有递归函数帮我们处理 ([l,mid]) 和 ([mid+1,r]) 的顺序问题，只需要为 ([l,r]) 外面的区间服务即可。
代码放的是处理贡献的部分。
Code
int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
memset(sum, 0, sizeof(sum));
for (int i = l; i <= r; i++) sum[i] = sum[i - 1] + a[i].x;
int i = l - 1;
for (int j = mid + 1; j <= r; j++) {
while (a[i + 1].x <= a[j].x && i < mid)
i++;
ans += a[j].v * ((i - l + 1) * a[j].x - sum[i] + sum[mid] - sum[i] - (mid - i) * a[j].x);
}