← 返回题目列表

Codeforces · 2176/E

E. 以最低成本移除

中文机器翻译题面 查看原题

您有 $$$n$$$ 个元素。每个元素都有一个自然值 $$$a_i$$$ 和一个自然移除成本 $$$c_i$$$。您需要删除除一个元素之外的所有元素,并付出尽可能小的成本。为此,您需要执行以下操作 $$$n - 1$$$ 次:

在一项操作中,您选择两个相邻元素并删除值较小的一个。对于此操作,您需要支付两者中最便宜的元素的移除成本。如果这两个元素具有相同的值,则可以删除其中任何一个,并按照删除成本支付两者中最小值的删除成本。删除一个元素后,被删除元素右侧的元素左移一位,不留间隙。

您还可以对数组的移除成本进行 $$$n$$$ 归零操作。在第 $$$i$$$ 归零操作之后,索引为 $$$p_i$$$ 的元素的移除成本变为 $$$0$$$。保证所有 $$$p_i$$$ 都是不同的。您需要针对原始元素以及每次归零操作后解决此问题。

注意:在第 $$$i$$$ 归零操作之后,元素 $$$p_i$$$ 的移除成本在所有后续问题中仍为 $$$0$$$ ($$$i + 1, i + 2, \dots, n$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个自然数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 您拥有的元素数量。

每个测试用例的第二行包含 $$$n$$$ 自然数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 元素的值。

每个测试用例的第三行包含 $$$n$$$ 自然数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — 元素的移除成本。

每个测试用例的第四行包含 $$$n$$$ 自然数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) - 删除成本为零的元素的索引,按相应的顺序。保证所有 $$$p_i$$$ 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n + 1$$$ 数字 - 在所有归零之前和每个归零之后删除除一个之外的所有元素的最小成本。

示例

输入
复制

2
10
5 5 8 10 4 3 4 10 5 5
10 3 9 6 9 8 7 8 10 3
1 10 2 9 5 6 7 4 3 8
4
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 2 4 3

输出
复制

42 36 30 30 30 12 12 12 0 0 0
3000000000 0 0 0 0

注意

第一个测试用例示例说明:

在归零之前删除所有元素的最小成本为 — 42。

要实现此成本,您可以例如:

  • 删除数组的第一个和第二个元素,成本为 $$$3$$$。这些是元素 ($$$5,10$$$) 和 ($$$5, 3$$$) - $$$\textbf{(value, cost)}$$$。然后我们可以先删除元素 ($$$5,10$$$),以获取第二个元素的成本 — $$$3$$$,因为第二个元素的值等于第一个元素的值。接下来,我们可以选择剩余元素 ($$$5,3$$$) 和元素 ($$$8,9$$$)(删除之前数组中的第三个元素)。值 $$$5 \le 8$$$,因此元素 ($$$5,3$$$) 也被删除,成本为 $$$3$$$。
  • 删除数组的最后两个元素 ($$$5,10$$$) 和 ($$$5,3$$$)。它们的移除成本为 $$$3$$$。
  • 可以使用元素 ($$$10,6$$$) — 原始数组中的第四个元素来删除数组的剩余元素。该元素的值大于或等于所有剩余元素的值,因此可以删除数组的所有剩余元素,成本为 $$$6$$$。元素 ($$$10,6$$$) 本身不会被删除,并将保留为数组的最后一个元素。

所有移除元素的总成本为$$$3+3+6+6+6+6+6+3+3=42$$$。可以证明,以较低的成本去除除一个元素之外的所有元素是不可能的。

在第一个归零请求之后,第一个元素变为 ($$$5, 0$$$)。现在可以删除的前两个元素不是 $$$3+3$$$,而是 $$$0+0$$$。现在,删除除一个元素之外的所有元素的总成本为 $$$36$$$。