Monsters (hard version) (Codeforces 1785C)
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):
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):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0

def op(a, b):
    return max(a, b)
e = -10 ** 9

def mapping(f, x):
    return f + x

def comp(f, g):
    return f + g
id = 0

def naive(n, a):
    ans = []
    for i in range(n):
        b = a[:i + 1]
        b = sorted(b)
        ans1 = 0
        res = 1
        for i in b:
            if res <= i:
                ans1 += i - res
                res += 1
        ans.append(ans1)
    return ans

def solve(n, a):
    ans = []
    res = 0
    now = 1
    mx = 0
    seg = lazy_segtree([-i for i in range(n + 5)], op, e, mapping, comp, id)
    for i in a:
        mx = max(i, mx)
        ''
        seg.apply(i, n + 3, 1)
        if seg.all_prod() >= 1:

            def f(x):
                return x <= 0
            r = seg.max_right(0, f)
            res -= r
            seg.apply(r, n + 3, -1)
            res += i
        else:
            res += i - now
            now += 1
        ans.append(res)
    return ans
for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(*solve(n, a))
import random
while False:
    n = random.randint(4, 100)
    a = [random.randint(1, n) for i in range(n)]
    if naive(n, a) != solve(n, a):
        print(n)
        print(a)
        print(naive(n, a), solve(n, a))
        exit()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0

def op(a, b):
    return max(a, b)
e = -10 ** 9

def mapping(f, x):
    return f + x

def comp(f, g):
    return f + g
id = 0

def naive(n, a):
    ans = []
    for i in range(n):
        b = a[:i + 1]
        b = sorted(b)
        ans1 = 0
        res = 1
        for i in b:
            if res <= i:
                ans1 += i - res
                res += 1
        ans.append(ans1)
    return ans

def solve(n, a):
    ans = []
    res = 0
    now = 1
    mx = 0
    seg = lazy_segtree([-i for i in range(n + 5)], op, e, mapping, comp, id)
    for i in a:
        mx = max(i, mx)
        ''
        seg.apply(i, n + 3, 1)
        if seg.all_prod() >= 1:

            def f(x):
                return x <= 0
            r = seg.max_right(0, f)
            res -= r
            seg.apply(r, n + 3, -1)
            res += i
        elif mx >= now:
            res += i - now
            now += 1
        else:
            res += i
        ans.append(res)
    return ans
for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(*solve(n, a))
import random
while False:
    n = random.randint(4, 100)
    a = [random.randint(1, n) for i in range(n)]
    if naive(n, a) != solve(n, a):
        print(n)
        print(a)
        print(naive(n, a), solve(n, a))
        exit()