Median Heap

题目描述

注意：本题的时间限制为 4s，是默认时间限制的两倍。 农夫约翰有一棵包含 $N$ 个节点的二叉树，节点编号为 $1$ 到 $N$（$1 \leq N < 2\cdot 10^5$ 且 $N$ 为奇数）。对于 $i>1$，节点 $i$ 的父节点为 $\lfloor i/2\rfloor$。每个节点有一个初始整数值 $a_i$，以及将该初始值改为任意其他整数值所需的代价 $c_i$（$0\le a_i,c_i\le 10^9$）。 他被联邦牛中介（FBI）要求在这棵树中寻找一个近似的中位数值，并设计了一个巧妙算法来实现。 他从最后一个节点 $N$ 开始，按编号递减向前处理。在算法的每一步中，若某个节点的值不是它与其两个子节点这三者的中位数，他就交换当前节点的值与“会成为中位数的那个子节点”的值。算法结束后，节点 $1$（根）的值就是近似中位数。 FBI 还给了农夫约翰一个包含 $Q$ 个（$1 \leq Q \leq 2\cdot 10^5$）相互独立的询问列表，每个询问给定一个目标值 $m$（$0\le m\le 10^9$）。对于每个询问，FJ 会先修改一些节点的初始值，然后执行上述近似中位数算法。对于每个询问，求使算法输出等于 $m$ 所需的最小总代价。

输入格式

第一行输入 $N$。 接下来 $N$ 行，每行包含两个整数 $a_i$ 和 $c_i$。 下一行包含 $Q$。 接下来 $Q$ 行，每行包含一个目标值 $m$。

输出格式

输出 $Q$ 行，每行对应一个目标值 $m$ 的最小可能总代价。

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

111
101
101
100
100
100
100
0
11
11
111

提示

要使近似中位数等于 $40$，FJ 可以将节点 3 的值改为 $60$。这会花费 $c_3=100$。 要使近似中位数等于 $45$，FJ 可以将节点 3 的值改为 $60$，并将节点 5 的值改为 $45$。这会花费 $c_3+c_5=100+1=101$。 SCORING: 输入 2-4：$N,Q\le 50$ 输入 5-7：$N,Q\le 1000$ 输入 8-16：无额外限制 题目贡献者：Suhas Nagar 和 Benjamin Qi

标签: USACO|2025|Gold

来源

USACO|2025|Gold