← 返回题目列表

Codeforces · 2234/F

F. 船只、高度和两个版本(硬版)

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

这是问题的困难版本。版本之间的差异在于,在此版本中,对 $$$n$$$ 和测试用例数量的约束更高。只有解决了该问题的所有版本,您才能破解。

有 $$$n$$$ 个无限高度的连通器排列成一个圆圈。每个容器的底面积为 $$$1$$$ cm$$$^2$$$,并且在第 $$$i$$$ 个容器和第 $$$(i \bmod n) + 1$$$ 个容器之间,在高度 $$$h_i$$$ cm 处存在可忽略不计的体积连接。对于每个容器 $$$i$$$,求在第 $$$i$$$ 个容器保持空的情况下,可以放入这些容器中的最大总水体积(以 cm$$$^3$$$ 为单位)。

正式地,你会得到一个数组 $$$h_1, h_2, \ldots, h_n$$$。如果满足以下条件,则非负整数 $$$w_1, w_2, \ldots, w_n$$$ 的循环数组被称为良好:

  • 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,如果 $$$\max(w_i, w_{i \bmod n + 1}) \gt h_i$$$,则 $$$w_i = w_{i \bmod n + 1}$$$。换句话说,如果数组$$$w$$$的两个相邻元素的最大值超过了数组$$$h$$$对应的元素,那么数组$$$w$$$的这两个相邻元素一定相等。

对于从$$1$$$到$$$n$$$的每个$$$i$$$,在$$$w_i = 0$$$的条件下,输出所有好数组$$$w_1、w_2、\ldots、w_n$$$中可能的最大总和$$$w_1 + w_2 + \ldots + w_n$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 船只数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — 容器之间的分区的高度。

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

输出

对于每个测试用例,输出 $$$n$$$ 个整数 - 第 $$$l$$$ 个整数表示在第 $$$l$$$ 个容器保持空的情况下,容器中的最大水总量(以 cm$$$^3$$$ 为单位)。

示例

输入
复制

4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5

输出
复制

6 6 7 9
17 16 14 14 17
21 21 20 20 21 21
17 17 17 17 21 21 22

注意

考虑第一个测试用例。

  • 为了保持容器 $$$1$$$ 为空,一个好的数组是 $$$w = [0, 1, 2, 3]$$$,总共有 $$$6$$$ cm$$$^3$$$ 的水。
  • 为了保持容器 $$$2$$$ 为空,一个好的数组是 $$$w = [1, 0, 2, 3]$$$,总共有 $$$6$$$ cm$$$^3$$$ 的水。
  • 为了保持容器 $$$3$$$ 为空,一个好的数组是 $$$w = [2, 2, 0, 3]$$$,总共 $$$7$$$ cm$$$^3$$$ 水。
  • 为了保持容器 $$$4$$$ 为空,一个好的数组是 $$$w = [3, 3, 3, 0]$$$,总共 $$$9$$$ cm$$$^3$$$ 水。

例如,数组 $$$w = [2, 2, 0, 4]$$$ 不好,因为 $$$\max(w_3, w_4) \gt h_3$$$,因此 $$$w_3 = w_4$$$ 必须成立。

可以证明,上面的每个数组在所有合适的选项中都具有最大可能的总和。