题意分析

Farmer John 的 N 头奶牛每年都会参加一个名为 "MooFest" 的社交聚会。在聚会上，奶牛们会进行各种活动，包括干草堆叠、跳栅栏、给农民贴尾巴，当然还有哞哞叫。由于年复一年地参加这些活动，一些奶牛的听力有所下降。

每头奶牛 i 都有一个与之相关的“听力”阈值 v(i)（范围在 1 到 20,000 之间）。如果一头奶牛对奶牛 i 哞叫，她必须使用至少 v(i) 乘以两头奶牛之间的距离的音量，以便奶牛 i 能够听到。如果两头奶牛 i 和 j 想要交谈，她们必须以等于她们之间距离乘以 $max(v(i), v(j))$的音量水平说话。

假设 N 头奶牛都站在一条直线上（每头奶牛在 1 到 20,000 之间的唯一 x 坐标上），并且每一对奶牛都在用尽可能小的音量进行交谈。

计算所有交谈的奶牛对产生的音量总和。

解题思路

1. 排序：首先，我们需要根据奶牛的音量阈值 v 对奶牛进行排序。这是因为我们需要确保在处理每对奶牛时，能够高效地计算它们之间的音量贡献。

2. 树状数组：使用两个树状数组（Fenwick Tree）来高效地维护和查询奶牛的数量和 x 坐标的和。这有助于我们快速计算在某个 x 坐标之前或之后的奶牛数量和它们的 x 坐标和。

3. 计算音量贡献：对于每头奶牛，计算它与之前所有奶牛的音量贡献。具体来说，对于当前奶牛 i，我们需要：

   • 计算在 x 坐标小于等于当前奶牛 x 坐标的奶牛数量（cnt）。
   • 计算这些奶牛的 x 坐标和（sum）。
   • 计算所有奶牛的 x 坐标和（tsum）。
   • 根据公式计算当前奶牛与之前奶牛的音量贡献，并累加到总和中。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 20005

struct node {
    int v, x;
} p[N];

long long cnum[N], clen[N];

int cmp(const void* a, const void* b) {
    return (*(struct node*)a).v - (*(struct node*)b).v;
}

int lowbit(int k) {
    return (-k) & k;
}

void update(long long c[], int k, int detal) {
    for (; k < N; k += lowbit(k))
        c[k] += detal;
}

long long getsum(long long c[], int k) {
    long long s = 0;
    for (; k > 0; k -= lowbit(k))
        s += c[k];
    return s;
}

int main(void) {
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(cnum, 0, sizeof(cnum));
        memset(clen, 0, sizeof(clen));
        for (int i = 1; i <= n; i++)
            scanf("%d %d", &p[i].v, &p[i].x);
        qsort(p + 1, n, sizeof(p[0]), cmp);
        long long ans = 0;
        update(cnum, p[1].x, 1);
        update(clen, p[1].x, p[1].x);
        for (int i = 2; i <= n; i++) {
            long long cnt = getsum(cnum, p[i].x);
            long long sum = getsum(clen, p[i].x);
            long long tsum = getsum(clen, N - 1);
            ans += p[i].v * (cnt * p[i].x - sum + tsum - sum - (i - cnt - 1) * p[i].x);
            update(cnum, p[i].x, 1);
            update(clen, p[i].x, p[i].x);
        }
        printf("%lld\n", ans);
    }
    return 0;
}