Monsters (hard version) (Codeforces 1786E)
Tags: Others, 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):
import io, os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class segment_tree(object):

    def merge(self, num, minimum):
        return min(minimum, num)

    def __init__(self, n):
        self.layer = (n - 1).bit_length()
        newn = 1 << self.layer
        self.n = newn
        self.arr = [0] * (2 * newn)
        self.lazy = [0] * newn
        for i in range(newn - 1, -1, -1):
            self.arr[i] = self.merge(self.arr[2 * i], self.arr[2 * i + 1])

    def rebuild(self, index):
        index = index >> 1
        while index > 0:
            self.arr[index] = self.merge(self.arr[index << 1], self.arr[index << 1 | 1]) + self.lazy[index]
            index = index >> 1

    def addtarget(self, index, target):
        self.arr[index] += target
        if index < self.n:
            self.lazy[index] += target

    def update(self, left, right, target):
        (i, j) = (self.n + left, self.n + right)
        (i0, j0) = (i, j)
        while i < j:
            if i & 1:
                self.addtarget(i, target)
                i += 1
            if not j & 1:
                self.addtarget(j, target)
                j -= 1
            i = i >> 1
            j = j >> 1
        if i == j:
            self.addtarget(i, target)
        self.rebuild(i0)
        self.rebuild(j0)

    def pushdown(self, index):
        for move in range(self.layer, 0, -1):
            father = index >> move
            if father < 1 or father >= self.n:
                continue
            if self.lazy[father] == 0:
                continue
            child = father << 1
            self.arr[child] += self.lazy[father]
            self.arr[child + 1] += self.lazy[father]
            if child < self.n:
                self.lazy[child] += self.lazy[father]
            if child + 1 < self.n:
                self.lazy[child + 1] += self.lazy[father]
            self.lazy[father] = 0

    def query(self, left, right):
        (i, j) = (self.n + left, self.n + right)
        output = 2147483647
        self.pushdown(i)
        self.pushdown(j)
        while i < j:
            if i & 1:
                output = self.merge(self.arr[i], output)
                i += 1
            if not j & 1:
                output = self.merge(self.arr[j], output)
                j -= 1
            i = i >> 1
            j = j >> 1
        if i == j:
            output = self.merge(self.arr[i], output)
        return output

def main(t):
    n = int(input())
    arr = list(map(int, input().split()))
    ans = []
    seg = segment_tree(n)
    accu = 0
    curr = -1
    for i in range(n):
        arr[i] -= 1
        seg.update(0, arr[i], 1)
        front = 0
        rear = curr + 2
        while front < rear:
            mid = (front + rear) // 2
            if seg.query(0, mid) > 0:
                front = mid + 1
            else:
                rear = mid
        if front - 1 > curr:
            curr += 1
            accu += arr[i] - curr
        else:
            accu += arr[i] - (front - 1)
        seg.update(0, front - 1, -1)
        ans.append(accu)
    print(*ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

Solution (Python):
import collections
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class SortedList:

    def __init__(self, iterable=None, _load=200):
        """"""
        values = [] if iterable is None else sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))
TC = int(input())
for tcx in range(TC):
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N + 1)
    for a in A:
        C[a] += 1
    result = 0
    q = collections.deque()
    for i in range(1, len(C)):
        while C[i] > 0 and q:
            t = q.popleft()
            result += i - t
            C[i] -= 1
            C[t] += 1
        if C[i] == 0:
            q.append(i)
    SL = SortedList([])
    max_val = 0
    for i in range(1, len(C)):
        if C[i] > 0:
            max_val = i
        if C[i] > 1:
            SL.add(i)
    R = [result]
    for i in range(N - 1, 0, -1):
        if C[A[i]] == 1:
            x = SL.bisect_right(A[i])
            if x == len(SL):
                R.append(R[-1] + max_val - A[i])
                C[max_val] -= 1
                max_val -= 1
            else:
                t = SL[x]
                R.append(R[-1] + t - A[i])
                C[t] -= 1
                if C[t] == 1:
                    SL.remove(t)
        elif C[A[i]] == 0:
            R.append(R[-1] + max_val - A[i])
            C[max_val] -= 1
            max_val -= 1
        else:
            R.append(R[-1])
            if C[A[i]] == 2:
                SL.remove(A[i])
            C[A[i]] -= 1
    print(*reversed(R))

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write

def debug(*args):
    if os.environ.get('debug') in [None, '0']:
        return
    from inspect import currentframe, getframeinfo
    from re import search
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

def solve(N, A):
    idx = sorted(list(range(N)), key=lambda i: A[i])
    tar = [-1] * N
    spare = {}
    cost = cur = 0
    for i in idx:
        if A[i] > cur:
            cur += 1
        cost += A[i] - cur
        tar[i] = cur
        spare[cur] = spare.get(cur, -1) + 1
    dup = SortedList((tar for (tar, cnt) in spare.items() if cnt))
    res = [cost]
    mx = tar[idx[-1]]
    for i in range(N - 1, 0, -1):
        (a, t) = (A[i], tar[i])
        cost -= a - t
        if t in dup:
            spare[t] -= 1
            if not spare[t]:
                dup.remove(t)
        else:
            j = dup.bisect_left(t)
            if j == len(dup):
                cost += mx - t
                mx -= 1
            else:
                nxt = dup[j]
                cost += nxt - t
                spare[nxt] -= 1
                if not spare[nxt]:
                    dup.remove(nxt)
        res.append(cost)
    return res[::-1]

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        res = solve(N, A)
        print(*res)
if __name__ == '__main__':
    main()