P5094 题解 分治

· · 题解

Description

给定两个长度为 n 的序列 v_i,x_i，定义一个点对 (i,j)（i \ne j）的价值 f(i,j) 为 \max(v_i,v_j) \times |x_i-x_j|，求：

\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i,j)[i \ne j]

Solution

很难想象这只是一个绿题，可能拿树状数组做会舒服一点吧，这里介绍分治做法。

我们把 \displaystyle \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i,j)[i \ne j] 先拆成 \displaystyle \sum\limits_{i=1}^n\sum\limits_{j=1}^n \max(v_i,v_j)[i \ne j] 和 \displaystyle \sum\limits_{i=1}^n \sum\limits_{j=1}^n |x_i-x_j|[i \ne j]，看看分别怎么计算：

\begin{aligned}\sum\limits_{i=1}^{j-1}|x_i-x_j|&=\sum\limits_{i=1}^{j-1}x_j-x_i\\&=\sum\limits_{i=1}^{j-1}x_j -\sum\limits_{i=1}^{j-1}x_i\\&=x_j \times (j-1)-sum_{j-1}\end{aligned}

其中 sum_i 为前缀和。

那把这两个融合起来怎么搞呢？我们可以用结构体输入这两个序列，以 v 为第一关键字先把序列进行排序。

现在对于区间 [l,r] 计算他的贡献，这一段区间的 v 是已经排好序的，所以考虑分治，将区间分为两半 [l,mid] 和 [mid+1,r]，可以通过递归算出贡献在 [l,mid] 的和贡献在 [mid+1,r] 的，接下来要算的就是有贡献的跨越这两个区间的。

我们在 [mid+1,r] 中枚举 j 作为贡献的右界，算 [l,j] 的贡献，并将其加起来作为跨区间的贡献和。将其分拆为 v 和 x 两部分计算：

\begin{aligned}x_j-x_l+x_j-x_{l+1}+\cdots+x_j-x_i+x_{i+1}-x_j+\cdots+x_{mid}-x_j&=\sum\limits_{k=l}^i x_j-x_k+\sum\limits_{k=i+1}^{mid} x_k-x_j\\&=\sum\limits_{k=l}^i x_j-\sum\limits_{k=l}^i x_k+\sum\limits_{k=i+1}^{mid} x_k-\sum\limits_{k=i+1}^{mid} x_j\\&=x_j \times (i-l+1)-sumx_{[l,i]}+sumx_{[i+1,mid]}-x_j \times (mid -i)\end{aligned}

通过预处理前缀和这个是可以 \mathcal O(1) 求的，也就是对于一个 j，他对答案的贡献为：

v_j \times (x_j \times (i-l+1)-sumx_{[l,i]}+sumx_{[i+1,mid]}-x_j \times (mid -i))

但注意，能将其如上计算的前提是 [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);
}