310114: CF1784C. Monsters (hard version)
Memory Limit:512 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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