[USACO04OPEN] MooFest G

题意

$n$ 头奶牛，第 $i$ 头坐标 $x_i$ （互不相同）、听力 $v_i$ 。每对奶牛 $(i,j)$ 交流音量 = $\max\{v_i, v_j\} \times |x_i - x_j|$ 。求所有点对音量之和。

数据范围： $n \leqslant 2 \times 10^4$ ， $v_i, x_i \leqslant 2 \times 10^4$ 。

思路

一句话本质：音量公式里的 $\max\{v_i, v_j\}$ 是障碍——按 $v$ 排序后，处理每头牛时它和"前面所有牛"的贡献中 $\max$ 就是它自己的 $v$ ，问题退化成"对每个 $x_i$ ，统计前面牛中左边/右边的数量与坐标和"，用两个树状数组 $O(\log n)$ 完成。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 14:30
 * update_at: 2026-08-05 14:30
 */
// brute.cpp：小数据暴力解，O(n^2) 枚举所有点对按公式直接计算。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;

int n;
long long v[MAXN], x[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i] >> x[i];

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            long long dist = x[i] - x[j];
            if (dist < 0) dist = -dist;
            ans += max(v[i], v[j]) * dist;
        }

    cout << ans << '\n';

    return 0;
}

暴力枚举所有 $\binom{n}{2}$ 个点对， $O(n^2)$ ， $n = 2 \times 10^4$ 时 $2 \times 10^8$ 次计算，不可行。

$\max\{v_i, v_j\}$ 怎么消掉？

如果让听力小的先被处理，那它和听力大的牛配对时， $\max$ 一定是大的一方。把牛按 $v$ 从小到大排序，依次处理。处理到第 $i$ 头牛时，它和前面 $i-1$ 头牛的贡献都是 $v_i \times |x_i - x_j|$ —— $\max$ 被排序消掉了。

剩下的 $|x_i - x_j|$ 怎么统计？

对第 $i$ 头牛，它和前面所有牛的贡献：

v_i \times \sum_{j < i} |x_i - x_j|

绝对值拆成左右两边：坐标比 $x_i$ 小的牛（数量 $c_l$ 、坐标和 $s_l$ ）贡献 $x_i \cdot c_l - s_l$ ；坐标比 $x_i$ 大的牛（ $c_g$ 、 $s_g$ ）贡献 $s_g - x_i \cdot c_g$ 。于是只需要维护：前面牛的坐标中，小于某个值的数量与坐标和——标准的树状数组前缀查询。

为什么用两个树状数组？

坐标范围只有 $2 \times 10^4$ ，直接以坐标为下标：

bit_cnt 维护坐标出现次数（查 $c_l$ ）；
bit_sum 维护坐标值之和（查 $s_l$ ）。

查询 $x_i - 1$ 的前缀得到"左边"，总数减去左边得到"右边"：

cpp

1
2
3
4
5
6long long cnt_less = query(bit_cnt, x - 1);
long long sum_less = query(bit_sum, x - 1);
long long cnt_greater = cnt_all - cnt_less;      // cnt_all = i-1
long long sum_greater = sum_all - sum_less;

ans += 1LL * v * (x * cnt_less - sum_less + sum_greater - x * cnt_greater);

处理完当前牛再把它插入两个 BIT，保证"前面"的含义正确。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 14:30
 * update_at: 2026-08-05 14:30
 */
// 按 v 排序后，处理第 i 头牛时它和之前牛的贡献 max(v) 就是 v[i]，
// 用两个树状数组维护前面牛的坐标数量与坐标和，O(n log n) 统计。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;

int n;
struct Cow {
    int v, x;
};
Cow cows[MAXN];

long long bit_cnt[MAXN];   // 坐标出现次数
long long bit_sum[MAXN];   // 坐标值之和

bool cmp_v(const Cow& a, const Cow& b) {
    return a.v < b.v;
}

void add(long long* bit, int idx, long long val) {
    for (; idx <= MAXN; idx += idx & -idx) bit[idx] += val;
}

long long query(long long* bit, int idx) {
    long long res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> cows[i].v >> cows[i].x;

    sort(cows + 1, cows + n + 1, cmp_v);   // 按听力升序

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = cows[i].x;
        int v = cows[i].v;

        // 前面（v 更小）的牛中，x 小于当前坐标的数量与坐标和
        long long cnt_less = query(bit_cnt, x - 1);
        long long sum_less = query(bit_sum, x - 1);
        // 全部前面牛的数量与坐标和
        long long cnt_all = i - 1;
        long long sum_all = query(bit_sum, MAXN);
        // 剩下的就是 x 大于当前坐标的部分
        long long cnt_greater = cnt_all - cnt_less;
        long long sum_greater = sum_all - sum_less;

        // 贡献 = v * (x*数量 - 坐标和 + 坐标和 - x*数量)，绝对值拆成左右两边
        ans += 1LL * v * (x * cnt_less - sum_less + sum_greater - x * cnt_greater);

        // 把当前牛插入 BIT
        add(bit_cnt, x, 1);
        add(bit_sum, x, x);
    }

    cout << ans << '\n';

    return 0;
}

复杂度

排序 $O(n \log n)$ ，每头牛两次查询 + 两次更新 $O(\log n)$ ，总 $O(n \log n)$ 。空间 $O(n)$ 。

总结

这题的核心套路是按排序消掉 $\max$ ：公式里有 $\max\{v_i, v_j\}$ 这种"看双方"的量时，按它排序可以让处理到每个元素时只看它和前面的关系。剩下的"统计前面小于/大于某个值的数量与和"，是树状数组的经典场景。

图示解析

这张图展示按 v 排序后，处理第 4 头牛时前面牛的统计：

text

1
2
3
4
5
6
7
8按 v 排序后的牛： (v,x)
  (2,6) (2,5) (3,1) (4,3)
    ↑     ↑     ↑     ↑
   已插入 BIT    当前牛 v=4, x=3

前面牛中：x < 3 的有 (3,1)  → cnt_less=1, sum_less=1
          x > 3 的有 (2,6),(2,5) → cnt_greater=2, sum_greater=11
贡献 = 4 × [(3×1-1) + (11-3×2)] = 4 × (2+5) = 28

读图方法：每头牛只和前面（v 更小）的牛配对， $\max$ 就是它自己的 v；绝对值靠"左边坐标和"和"右边坐标和"分别结算，两个 BIT 各司其职。

[USACO04OPEN] MooFest G

目录

题意

思路

代码

复杂度

总结

图示解析