CF2176E Remove at the lowest cost

你有 $n$ 个元素。每个元素有一个自然值 $a_i$ 和一个自然删除代价 $c_i$。你需要将除一个以外的所有元素移除，并且总支付的费用最小。为此，你可以进行如下操作 $n-1$ 次： 每次操作，你选择两个相邻的元素，移除值较小的那个。在这次操作中，你需要支付这两个元素中删除代价较小的那一个。如果这两个元素的值相等，你可以移除任意一个，支付二者中较小的删除代价。移除一个元素后，其右侧的所有元素会向左移动一位，不留空隙。 你还有 $n$ 次将数组中某个元素删除代价变为 $0$ 的操作。第 $i$ 次操作后，下标为 $p_i$ 的元素的删除代价变为 $0$。保证所有 $p_i$ 互不相同。你需要分别求出原数组，以及每次将删除代价赋为 $0$ 之后的最小总移除费用。 注意：第 $i$ 次操作后，下标为 $p_i$ 的元素在之后所有问题（$i+1, i+2, \dots, n$）中的删除代价都保持为 $0$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示元素个数。 第二行包含 $n$ 个自然数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每个元素的值。 第三行包含 $n$ 个自然数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq 10^9$），表示每个元素的移除代价。 第四行包含 $n$ 个自然数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示在对应操作中，哪一个元素的移除代价会变成 $0$。保证所有 $p_i$ 互不相同。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出 $n+1$ 个数，分别表示在执行所有置零操作之前以及每次操作后，移除除一个外所有元素的最小总代价。

样例第一组测试数据说明： 在所有置零操作之前的最小总代价是 $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$，被保留的元素不会被消除。 所有被移除元素的总代价是 $3+3+6+6+6+6+6+3+3=42$。可以证明，没有更小的移除费用了。 第一步置零后，第一个元素变为 $(5,0)$。此时前两个元素移除费用由原来的 $3+3$ 变为 $0+0$。此时移除除一个以外所有元素的最小总代价变为 $36$。 由 ChatGPT 5 翻译