[USACO04OPEN] MooFest G

题目描述

DESCRIPTION

Every year, Farmer John’s () 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 (in the range ). If a cow moos to cow , she must use a volume of at least times the distance between the two cows in order to be heard by cow . If two cows and wish to converse, they must speak at a volume level equal to the distance between them times .

Suppose each of the cows is standing in a straight line (each cow at some unique coordinate in the range ), 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 pairs of mooing cows.

INPUT FORMAT

Line : A single integer,

Lines : Two integers: the volume threshold and x coordinate for a cow. Line represents the first cow; line represents the second cow; and so on. No two cows will stand at the same location.

OUTPUT FORMAT

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

SAMPLE INPUT

SAMPLE OUTPUT

题目大意

给定两个长度为的序列，求

题解

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

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

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

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

考虑与有关的这个式子，将绝对值展开可以获得:

要想计算前一半区间对后一半区间的贡献，我们需要对后一半区间的每一个点枚举前一半区间里所有点到该点的距离和，即

归并排序的同时计算即可，时间复杂度 .

代码实现

#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;
}