Monsters (hard version)

题意翻译

你面前有 $n$ 个怪兽，第 $i$ 个怪兽的生命值是 $a_i$。你有两种操作可以使用： 操作一：选择一只怪物，造成一点伤害。 操作二：对所有怪物造成一点伤害，若有怪物因为此操作生命值降为零，则重复次操作一次。 操作二只能使用一次，求出能令所有怪物生命值降到零及以下的最小操作一的次数。

题目描述

This is the hard version of the problem. In this version, you need to find the answer for every prefix of the monster array. In a computer game, you are fighting against $ n $ monsters. Monster number $ i $ has $ a_i $ health points, all $ a_i $ are integers. A monster is alive while it has at least $ 1 $ health point. You can cast spells of two types: 1. Deal $ 1 $ damage to any single alive monster of your choice. 2. Deal $ 1 $ damage to all alive monsters. If at least one monster dies (ends up with $ 0 $ health points) as a result of this action, then repeat it (and keep repeating while at least one monster dies every time). Dealing $ 1 $ damage to a monster reduces its health by $ 1 $ . Spells of type 1 can be cast any number of times, while a spell of type 2 can be cast at most once during the game. For every $ k = 1, 2, \ldots, n $ , answer the following question. Suppose that only the first $ k $ monsters, with numbers $ 1, 2, \ldots, k $ , are present in the game. What is the smallest number of times you need to cast spells of type 1 to kill all $ k $ monsters?

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. Each test case consists of two lines. The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of monsters. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — monsters' health points. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print $ n $ integers. The $ k $ -th of these integers must be equal to the smallest number of times you need to cast spells of type 1 to kill all $ k $ monsters, if only monsters with numbers $ 1, 2, \ldots, k $ are present in the game.

输入输出样例

输入样例 #1

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

输出样例 #1

2 1 0
3 2 4 4 4 4

说明

In the first test case, for $ k = n $ , the initial health points of the monsters are $ [3, 1, 2] $ . It is enough to cast a spell of type 2: - Monsters' health points change to $ [2, 0, 1] $ . Since monster number $ 2 $ dies, the spell is repeated. - Monsters' health points change to $ [1, 0, 0] $ . Since monster number $ 3 $ dies, the spell is repeated. - Monsters' health points change to $ [0, 0, 0] $ . Since monster number $ 1 $ dies, the spell is repeated. - Monsters' health points change to $ [0, 0, 0] $ . Since it is possible to use no spells of type 1 at all, the answer is $ 0 $ . In the second test case, for $ k = n $ , the initial health points of the monsters are $ [4, 1, 5, 4, 1, 1] $ . Here is one of the optimal action sequences: - Using a spell of type 1, deal $ 1 $ damage to monster number $ 1 $ . Monsters' health points change to $ [3, 1, 5, 4, 1, 1] $ . - Using a spell of type 1, deal $ 1 $ damage to monster number $ 4 $ . Monsters' health points change to $ [3, 1, 5, 3, 1, 1] $ . - Using a spell of type 1, deal $ 1 $ damage to monster number $ 4 $ again. Monsters' health points change to $ [3, 1, 5, 2, 1, 1] $ . - Use a spell of type 2: - Monsters' health points change to $ [2, 0, 4, 1, 0, 0] $ . Since monsters number $ 2 $ , $ 5 $ , and $ 6 $ die, the spell is repeated. - Monsters' health points change to $ [1, 0, 3, 0, 0, 0] $ . Since monster number $ 4 $ dies, the spell is repeated. - Monsters' health points change to $ [0, 0, 2, 0, 0, 0] $ . Since monster number $ 1 $ dies, the spell is repeated. - Monsters' health points change to $ [0, 0, 1, 0, 0, 0] $ . - Using a spell of type 1, deal $ 1 $ damage to monster number $ 3 $ . Monsters' health points change to $ [0, 0, 0, 0, 0, 0] $ . Spells of type 1 are cast $ 4 $ times in total. It can be shown that this is the smallest possible number.

**题目大意：**

这个问题是“怪兽（困难版本）”的问题。在这个版本中，你需要找出对于怪兽数组的每个前缀的答案。

在一个电脑游戏中，你正在对抗 $ n $ 个怪兽。第 $ i $ 个怪兽拥有 $ a_i $ 的生命值，所有的 $ a_i $ 都是整数。只要怪兽至少有 $ 1 $ 点生命值，它就是存活的。

你可以施展两种类型的咒语：

1. 对你选择的任意一个存活的怪兽造成 $ 1 $ 点伤害。
2. 对所有存活的怪兽造成 $ 1 $ 点伤害。如果至少有一个怪兽因此动作而死亡（生命值降到 $ 0 $ 点），则重复此动作（只要每次至少有一个怪兽死亡，就继续重复）。

对怪兽造成 $ 1 $ 点伤害会使其生命值减少 $ 1 $ 点。

类型 1 的咒语可以使用任意多次，而类型 2 的咒语在游戏中最多只能使用一次。

对于每个 $ k = 1, 2, \ldots, n $ ，回答以下问题。假设游戏中只存在前 $ k $ 个怪兽，编号为 $ 1, 2, \ldots, k $ ，你需要施展类型 1 的咒语的最小次数是多少才能杀死所有 $ k $ 个怪兽？

**输入输出数据格式：**

**输入格式：**

每个测试包含多个测试案例。第一行包含测试案例的数量 $ t $ （ $ 1 \le t \le 10^4 $ ）。接下来是测试案例的描述。

每个测试案例由两行组成。第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——怪兽的数量。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ （ $ 1 \le a_i \le n $ ）——怪兽的生命值。

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

**输出格式：**

对于每个测试案例，打印 $ n $ 个整数。这些整数中的第 $ k $ 个数表示如果游戏中只存在编号为 $ 1, 2, \ldots, k $ 的怪兽，杀死所有 $ k $ 个怪兽所需施展的最小类型 1 咒语次数。**题目大意：** 这个问题是“怪兽（困难版本）”的问题。在这个版本中，你需要找出对于怪兽数组的每个前缀的答案。 在一个电脑游戏中，你正在对抗 $ n $ 个怪兽。第 $ i $ 个怪兽拥有 $ a_i $ 的生命值，所有的 $ a_i $ 都是整数。只要怪兽至少有 $ 1 $ 点生命值，它就是存活的。 你可以施展两种类型的咒语： 1. 对你选择的任意一个存活的怪兽造成 $ 1 $ 点伤害。 2. 对所有存活的怪兽造成 $ 1 $ 点伤害。如果至少有一个怪兽因此动作而死亡（生命值降到 $ 0 $ 点），则重复此动作（只要每次至少有一个怪兽死亡，就继续重复）。 对怪兽造成 $ 1 $ 点伤害会使其生命值减少 $ 1 $ 点。 类型 1 的咒语可以使用任意多次，而类型 2 的咒语在游戏中最多只能使用一次。 对于每个 $ k = 1, 2, \ldots, n $ ，回答以下问题。假设游戏中只存在前 $ k $ 个怪兽，编号为 $ 1, 2, \ldots, k $ ，你需要施展类型 1 的咒语的最小次数是多少才能杀死所有 $ k $ 个怪兽？ **输入输出数据格式：** **输入格式：** 每个测试包含多个测试案例。第一行包含测试案例的数量 $ t $ （ $ 1 \le t \le 10^4 $ ）。接下来是测试案例的描述。 每个测试案例由两行组成。第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——怪兽的数量。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ （ $ 1 \le a_i \le n $ ）——怪兽的生命值。 保证所有测试案例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。 **输出格式：** 对于每个测试案例，打印 $ n $ 个整数。这些整数中的第 $ k $ 个数表示如果游戏中只存在编号为 $ 1, 2, \ldots, k $ 的怪兽，杀死所有 $ k $ 个怪兽所需施展的最小类型 1 咒语次数。