[USACO04OPEN] MooFest G

题意

每对奶牛 $(i,j)$ 贡献 $\max(v_i,v_j)\lvert x_i-x_j\rvert$ ，求所有无序点对的贡献和。

思路

按听力 v 从小到大处理。轮到当前奶牛时，所有已处理奶牛的听力都不大于它，因此它与这些奶牛配对时的 max 就是当前 volume。

只需快速求当前坐标 x 到所有旧坐标的距离和。用两棵树状数组分别维护坐标前缀中的数量与坐标和：

text

1
2左侧距离和 = x * left_count - left_sum
右侧距离和 = right_sum - x * right_count

两部分相加后乘当前听力，就是当前奶牛新产生的全部贡献。

Python 知识

sorted((volume, position) for ...) 默认按元组字典序排序，正好先按听力排序。
一个 prefix(tree, index) 函数可复用于计数树和坐标和树。
Python 整数自动扩容，答案超过 64 位边界时也不会溢出。
多变量赋值 seen = position_sum = answer = 0 适合初始化同类累加器。

代码

python

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
35import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
cows = sorted((next(data), next(data)) for _ in range(n))
limit = max(position for _, position in cows) + 1
count_tree = [0] * (limit + 1)
sum_tree = [0] * (limit + 1)
seen = position_sum = answer = 0


def prefix(tree, index):
    result = 0
    while index:
        result += tree[index]
        index -= index & -index
    return result


for volume, position in cows:
    left_count = prefix(count_tree, position)
    left_sum = prefix(sum_tree, position)
    distance_sum = (position * left_count - left_sum
                    + position_sum - left_sum - position * (seen - left_count))
    answer += volume * distance_sum
    index = position
    while index <= limit:
        count_tree[index] += 1
        sum_tree[index] += position
        index += index & -index
    seen += 1
    position_sum += position

print(answer)

复杂度

排序 $O(n\log n)$ ，每头奶牛进行常数次树状数组操作，总时间 $O(n\log n)$ ；空间 $O(\max x_i)$ 。

总结

先排序固定 max(v_i,v_j) 由谁贡献，再用“数量 + 坐标和”拆绝对值，是本题的两个核心步骤。

[USACO04OPEN] MooFest G

目录

题意

思路

Python 知识

代码

复杂度

总结