Monsters (hard version) (Codeforces 1784C)
Tags: Greedy, data structures

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:  Deal $$$1$$$ damage to any single alive monster of your choice.  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?

Input: 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$$$.

Output: 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.

Note: 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.

Sample Inputs:
2
3
3 1 2
6
4 1 5 4 1 1

Sample Outputs:
2 1 0
3 2 4 4 4 4

Solution (Python):
from collections import *
from functools import *
import sys
from bisect import *
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    n = int(input())
    (*arr,) = map(int, input().split())
    poi = 1
    sum1 = 0
    sum2 = 0
    dic = {}
    invalid = {}
    ans = deque()
    orarr = sorted(arr)
    i = 1
    for j in orarr:
        if j >= i:
            dic[j] = dic.get(j, 0) + 1
            sum1 += i
            sum2 += j
            i += 1
        else:
            invalid[j] = invalid.get(j, 0) + 1
    i -= 1
    sum3 = sum2 - sum1
    rep = sorted(invalid.keys())
    for j in arr[::-1]:
        if invalid.get(j, 0) > 0:
            ans.appendleft(sum3)
            invalid[j] -= 1
            if invalid[j] == 0:
                rep.pop(rep.index(j))
        else:
            ans.appendleft(sum3)
            if rep and j < rep[-1]:
                k = bisect_right(rep, j)
                abc = rep[k]
                dic[abc] += 1
                invalid[abc] -= 1
                if invalid[abc] == 0:
                    rep.pop(k)
                sum2 = sum2 - j + abc
                sum3 = sum2 - sum1
            else:
                dic[j] -= 1
                sum1 -= i
                sum2 -= j
                i -= 1
                sum3 = sum2 - sum1
    print(*ans)

Solution (Python):
t = int(input())

def Eval(t):
    return t[0] + t[2]

def Select(t1, t2):
    if Eval(t1) <= Eval(t2):
        return (Eval(t1), t1[1], 0)
    return (Eval(t2), t2[1], 0)

class SegmentTree:

    def __init__(self, nn):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.arr = [0] * (2 * self.n)
        for i in range(self.n, 2 * self.n):
            self.arr[i] = (i - self.n, i - self.n, 0)
        for i in range(self.n - 1, 0, -1):
            self.arr[i] = min(self.arr[i * 2], self.arr[i * 2 + 1])

    def reset(self, nn):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        for i in range(self.n, 2 * self.n):
            self.arr[i] = (i - self.n, i - self.n, 0)
        for i in range(self.n - 1, 0, -1):
            self.arr[i] = min(self.arr[i * 2], self.arr[i * 2 + 1])

    def query(self):
        return self.arr[1]

    def push(self, x):
        if x >= self.n:
            return
        if self.arr[x][2] == 0:
            return
        self.arr[x * 2] = (self.arr[x * 2][0], self.arr[x * 2][1], self.arr[x * 2][2] + self.arr[x][2])
        self.arr[x * 2 + 1] = (self.arr[x * 2 + 1][0], self.arr[x * 2 + 1][1], self.arr[x * 2 + 1][2] + self.arr[x][2])
        self.arr[x] = Select(self.arr[x * 2], self.arr[x * 2 + 1])

    def change(self, lq, rq, v, nod=1, l=-1, r=-1):
        if l == -1:
            l = 0
            r = self.n
        if lq <= l and r <= rq:
            self.arr[nod] = (self.arr[nod][0], self.arr[nod][1], self.arr[nod][2] + v)
            return
        if lq >= r or rq <= l:
            return
        self.push(nod)
        m = (l + r) // 2
        self.change(lq, rq, v, nod * 2, l, m)
        self.change(lq, rq, v, nod * 2 + 1, m, r)
        self.arr[nod] = Select(self.arr[nod * 2], self.arr[nod * 2 + 1])
st = SegmentTree(200001)
for _ in range(t):
    n = int(input())
    st.reset(n)
    (cutil, suma) = (0, 0)
    for ai in map(int, input().split()):
        suma += ai
        cutil += 1
        st.change(ai, n + 1, -1)
        q = st.query()
        while Eval(q) < 0:
            cutil -= 1
            suma -= q[1]
            st.change(q[1], n + 1, 1)
            q = st.query()
        print(suma - cutil * (cutil + 1) // 2, end=' ')
    print('')

Solution (Python):
t = int(input())

def Eval(t):
    return t[0] + t[2]

def Select(t1: tuple[int, int, int], t2: tuple[int, int, int]):
    if Eval(t1) <= Eval(t2):
        return (Eval(t1), t1[1], 0)
    return (Eval(t2), t2[1], 0)

class SegmentTree:

    def __init__(self, nn):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        self.arr = [(0, 0, 0)] * (2 * self.n)
        for i in range(self.n, 2 * self.n):
            self.arr[i] = (i - self.n, i - self.n, 0)
        for i in range(self.n - 1, 0, -1):
            self.arr[i] = min(self.arr[i * 2], self.arr[i * 2 + 1])

    def reset(self, nn):
        self.n = 1
        while self.n < nn:
            self.n *= 2
        for i in range(self.n, 2 * self.n):
            self.arr[i] = (i - self.n, i - self.n, 0)
        for i in range(self.n - 1, 0, -1):
            self.arr[i] = min(self.arr[i * 2], self.arr[i * 2 + 1])

    def query(self):
        return self.arr[1]

    def push(self, x):
        if x >= self.n:
            return
        if self.arr[x][2] == 0:
            return
        self.arr[x * 2] = (self.arr[x * 2][0], self.arr[x * 2][1], self.arr[x * 2][2] + self.arr[x][2])
        self.arr[x * 2 + 1] = (self.arr[x * 2 + 1][0], self.arr[x * 2 + 1][1], self.arr[x * 2 + 1][2] + self.arr[x][2])

    def change(self, lq, rq, v, nod=1, l=-1, r=-1):
        if l == -1:
            l = 0
            r = self.n
        if lq <= l and r <= rq:
            self.arr[nod] = (self.arr[nod][0], self.arr[nod][1], self.arr[nod][2] + v)
            return
        if lq >= r or rq <= l:
            return
        self.push(nod)
        m = (l + r) // 2
        self.change(lq, rq, v, nod * 2, l, m)
        self.change(lq, rq, v, nod * 2 + 1, m, r)
        self.arr[nod] = Select(self.arr[nod * 2], self.arr[nod * 2 + 1])
st = SegmentTree(200001)
for _ in range(t):
    n = int(input())
    st.reset(n)
    (cutil, suma) = (0, 0)
    for ai in map(int, input().split()):
        suma += ai
        cutil += 1
        st.change(ai, n + 1, -1)
        q = st.query()
        while Eval(q) < 0:
            cutil -= 1
            suma -= q[1]
            st.change(q[1], n + 1, 1)
            q = st.query()
        print(suma - cutil * (cutil + 1) // 2, end=' ')
    print('')