[USACO04OPEN] MooFest G

题目描述

DESCRIPTION

Every year, Farmer John’s $N$ ($1 \leq N \leq 20,000$) cows attend “MooFest”,a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.

Each cow i has an associated “hearing” threshold $v(i)$ (in the range $1 \dots 20,000$). If a cow moos to cow $i$, she must use a volume of at least $v(i)$ times the distance between the two cows in order to be heard by cow $i$. If two cows $i$ and $j$ wish to converse, they must speak at a volume level equal to the distance between them times $max(v(i),v(j))$.

Suppose each of the $N$ cows is standing in a straight line (each cow at some unique $x$ coordinate in the range $1 \dots 20,000$), and every pair of cows is carrying on a conversation using the smallest possible volume.

Compute the sum of all the volumes produced by all $\frac{N \times (N-1)}{2}$ pairs of mooing cows.

INPUT FORMAT

Line $1$: A single integer, $N$

Lines $2 \dots N+1$: Two integers: the volume threshold and x coordinate for a cow. Line $2$ represents the first cow; line $3$ represents the second cow; and so on. No two cows will stand at the same location.

OUTPUT FORMAT

Line $1$: A single line with a single integer that is the sum of all the volumes of the conversing cows

SAMPLE INPUT

4
3 1
2 5
2 6
4 3

SAMPLE OUTPUT

57

题目大意

给定两个长度为 $n$ 的序列 $v_i, x_i$， 求$$ \sum_{i=1}^{n} \sum_{j=1}^{n} max(v_i, v_j) \times |x_i-x_j| (i \neq j)$$

题解

暴力枚举计算该式的复杂度为 $O(n^2)$, 在原题的数据范围和现在的评测机运算能力下是可以通过的，不过这道题还有更优的做法。

这是一个二维偏序问题，可以考虑使用CDQ分治的思想解决

分析原来的式子，发现计算该式的瓶颈在于 $max(v_i, v_j)$ ，考虑将原序列按照 $v_i$ 的值进行升序排列，对第二维进行分治

现在计算一段区间 $[l, r]$ 内的贡献 ，将区间分为 $[l, mid]$ 和 $[mid + 1, r]$ 两端，通过递归可以分别计算出其各自区间的总贡献，接下来要计算的就是跨越这两个区间的贡献

考虑与 $x$ 有关的这个式子 $|x_i-x_j|$ ，将绝对值展开可以获得:

$|x_i-x_j|= \begin{cases} x_i - x_j \quad x_i > x_j \\\\ x_j - x_i \quad x_i < x_j \end{cases}$

要想计算前一半区间 $[l, mid]$ 对后一半区间 $[mid + 1, r]$ 的贡献，我们需要对后一半区间的每一个点 $i$ 枚举前一半区间里所有点到该点的距离和，即

$Sum_i = \sum_{j = l}^{mid}{|x_i - x_j|} \\\\ = \sum_{j = l}^{mid}{[x_j < x_i](x_i - x_j)} + \sum_{j = l}^{mid}{[x_j > x_i](x_j - x_i)} \\\\ = (\sum_{j = l}^{mid}{[x_j < x_i]x_i} - \sum_{j = l}^{mid}{[x_j < x_i]x_j}) + (\sum_{j = l}^{mid}{[x_j > x_i]x_j} - \sum_{j = l}^{mid}{[x_j > x_i]x_i}) \\\\ = x_i \times \sum_{j = l}^{mid}[x_j < x_i] - \sum_{x_i > x_j}x_j + \sum_{x_i < x_j}x_j - x_i \times \sum_{j = l}^{mid}[x_j > x_i]$

归并排序的同时计算即可，时间复杂度 $O(nlogn)$.

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 5;

#define v first
#define x second

int n;
pair<int, int> a[N];

int sumx[N];
long long ans;
pair<int, int> tmp[N];
void mergesort(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    long long sum1 = 0, sum2 = 0;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    for (int i = l; i <= mid; i++)
        sum1 += a[i].x;
    for (int i = mid + 1, j = l; i <= r; i++)
    {
        while (j <= mid && a[j].x < a[i].x)
        {
            sum1 -= a[j].x;
            sum2 += a[j].x;
            j++;
        }
        ans += 1LL * a[i].v * (1LL * a[i].x * (j - l) - sum2 - 1LL * a[i].x * (mid - j + 1) + sum1);
    }
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (a[i].x < a[j].x)
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= r)
        tmp[k++] = a[j++];
    for (int p = 0; p < k; p++)
        a[l + p] = tmp[p];
    return;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].v, &a[i].x);
    sort(a + 1, a + n + 1);
    mergesort(1, n);
    printf("%lld\n", ans);
    return 0;
}