← 返回题目列表

Codeforces · 2151/C

C. 增量停留

中文机器翻译题面 查看原题
巨兽加农炮,Zef - 月鲸
⠀

你是博物馆的保安。

博物馆的正门既是入口也是出口。每秒最多可以有一个人进门。有一个传感器可以检测访客何时通过门。传感器既无法确定参观者是谁,也无法确定他是否进入或离开了博物馆。传感器在 $$$2n$$$ 不同时刻 $$$a_1, a_2, \ldots, a_{2n}$$$(以秒为单位)检测到一些活动。

对于每个访客来说,他的停留时间等于退出时间减去进入时间。

现在博物馆已关闭(因此没有游客),您想知道今天可能的最大总停留时间,即今天进入博物馆的所有游客可能的最大停留时间之和。第二次$$$0$$$,博物馆也关门了。

出于安全考虑,博物馆内同时停留的人数也有限制,但你忘记了这个限制。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,您想要确定今天可能的最大总停留时间,假设最多 $$$k$$$ 人可以同时留在博物馆。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$),表明传感器在 $$$2n$$$ 不同时刻检测到某些活动。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_{2n} \leq 10^9$$$) - 传感器检测到某些活动的秒数。

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

输出

对于每个测试用例,打印 $$$n$$$ 整数:对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,打印今天可能的最大总停留时间,假设最多 $$$k$$$ 人可以同时留在博物馆。

示例

输入
复制

3
1
32 78
2
4 5 6 9
4
6149048 26582657 36124499 43993239 813829899 860114890 910238130 913669539

输出
复制

46
4 6
78018749 1737022233 1845329695 3385003015

注意

在第一个测试用例中,传感器在 $$$32$$$ 和 $$$78$$$ 秒处检测到活动。回想一下,$$$k$$$ 是可以同时留在博物馆的最大人数。

  • 如果 $$$k$$$ 为 $$$1$$$,则最大可能总停留时间为 $$$46$$$,如果访客 $$$1$$$ 在时间 $$$32$$$ 进入并在时间 $$$78$$$ 退出,则达到该值。

在第二个测试用例中,传感器在 $$$4$$$、$$$5$$$、$$$6$$$ 和 $$$9$$$ 秒处检测到活动。

  • 如果 $$$k$$$ 为 $$$1$$$,则最大可能总停留时间为 $$$4$$$,如果访问者 $$$1$$$ 在时间 $$$4$$$ 进入并在时间 $$$5$$$ 退出,并且访问者 $$$2$$$ 在时间 $$$6$$$ 进入并在时间 $$$9$$$ 退出,则达到最大总停留时间。
  • 如果 $$$k$$$ 为 $$$2$$$,则最大可能总停留时间为 $$$6$$$,如果访问者 $$$1$$$ 在时间 $$$4$$$ 进入并在时间 $$$9$$$ 退出,并且访问者 $$$2$$$ 在时间 $$$5$$$ 进入并在时间 $$$6$$$ 退出,则达到最大总停留时间。