CF2151C.Incremental Stay

Danimal Cannon, Zef - The Lunar Whale

⠀

你是一家博物馆的安保人员。

博物馆的大门既是入口，也是出口。每秒最多只能有一人通过大门。门上有一个传感器能够检测到有访客通过，但无法判别该访客的身份，也无法判断是进馆还是出馆。传感器在 $2n$ 个不同的时刻 $a_1, a_2, \ldots, a_{2n}$（以秒为单位）检测到有人通过。

对于每个访客，他的停留时长等于离开时间减去进入时间。

现在博物馆已经关闭（馆内无访客），你想知道今天所有进入博物馆的访客们最大可能的总停留时长，也就是所有访客停留时长的最大可能和。第 $0$ 秒时，博物馆也是关闭的。

出于安全考虑，馆内同时在馆人数也有上限，但你记不清具体限制了。对于每一个 $k$，$1 \leq k \leq n$，你都希望知道：假设最多允许 $k$ 名访客同时在馆内，今天最大可能的总停留时长是多少。

每个测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据组数。

每组测试数据的第一行是一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示传感器检测到 $2n$ 个不同的时刻。

第二行给出 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1 \leq a_1 < a_2 < \ldots < a_{2n} \leq 10^9$），表示每次检测到有人通过门口时的时间（按严格递增顺序给出）。

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出 $n$ 个整数：对于每一个 $k$，$1 \leq k \leq n$，输出假设最多允许 $k$ 名访客同时在馆内时，今天最大可能的总停留时长。

在第一个测试样例中，传感器在 $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$ 秒离开。

由 ChatGPT 5 翻译