Minimize Inversions Number (Codeforces 1637H)
Tags: Greedy, sortings

You are given a permutation $$$p$$$ of length $$$n$$$.You can choose any subsequence, remove it from the permutation, and insert it at the beginning of the permutation keeping the same order.For every $$$k$$$ from $$$0$$$ to $$$n$$$, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly $$$k$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50\,000$$$) — the number of test cases.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the permutation.The second line of each test case contains the permutation $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^5$$$.

Output: For each test case output $$$n + 1$$$ integers. The $$$i$$$-th of them must be the answer for the subsequence length of $$$i - 1$$$.

Note: In the second test case:   For the length $$$0$$$: $$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.  For the length $$$1$$$: $$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$: $$$2$$$ inversions.  For the length $$$2$$$: $$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$, or $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ inversions.  For the length $$$3$$$: $$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$: $$$1$$$ inversion.  For the length $$$4$$$: $$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions. 

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

Sample Outputs:
0 0
4 2 2 1 4
5 4 2 2 1 5

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

class BIT:

    def __init__(self, n):
        self.n = n + 5
        self.arr = [0] * self.n

    def add(self, index):
        while index < self.n:
            self.arr[index] += 1
            index += index & -index

    def query(self, index):
        s = 0
        while index > 0:
            s += self.arr[index]
            index -= index & -index
        return s
(t,) = I()
for _ in range(t):
    (n,) = I()
    p = I()
    invs = 0
    bit = BIT(n)
    for i in range(n - 1, -1, -1):
        invs += bit.query(p[i])
        bit.add(p[i])
    c = [0] * n
    for i in range(n):
        c[i] = i + 2 - 2 * p[i]
    c.sort(reverse=True)
    s = 0
    out = [invs]
    for i in range(n):
        s += c[i]
        out.append(invs - s - i * (i + 1) // 2)
    print(*out)

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

def mergeinv(l):
    if len(l) == 1:
        return [0, l]
    mid = len(l) // 2
    (x, l1) = mergeinv(l[:mid])
    (y, l2) = mergeinv(l[mid:])
    ind1 = 0
    ind2 = 0
    out = []
    invs = x + y
    while ind1 < len(l1) or ind2 < len(l2):
        if ind1 == len(l1):
            out.append(l2[ind2])
            ind2 += 1
        elif ind2 == len(l2):
            out.append(l1[ind1])
            invs += ind2
            ind1 += 1
        elif l1[ind1] < l2[ind2]:
            out.append(l1[ind1])
            invs += ind2
            ind1 += 1
        else:
            out.append(l2[ind2])
            ind2 += 1
    return [invs, out]
(t,) = I()
for _ in range(t):
    (n,) = I()
    p = I()
    (invs, x) = mergeinv(p)
    c = [0] * n
    for i in range(n):
        c[i] = i + 2 - 2 * p[i]
    c.sort(reverse=True)
    s = 0
    out = [invs]
    for i in range(n):
        s += c[i]
        out.append(invs - s - i * (i + 1) // 2)
    print(*out)

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

class BIT:

    def __init__(self, n):
        self.n = n + 5
        self.arr = [0] * self.n

    def add(self, index):
        while index < self.n:
            self.arr[index] += 1
            index += index & -index

    def query(self, index):
        s = 0
        while index > 0:
            s += self.arr[index]
            index -= index & -index
        return s
(t,) = I()
for _ in range(t):
    (n,) = I()
    p = I()
    invs = 0
    bit = BIT(n)
    for i in range(n - 1, -1, -1):
        invs += bit.query(p[i])
        bit.add(p[i])
    c = [0] * n
    for i in range(n):
        c[i] = i + 2 - 2 * p[i]
    c.sort(reverse=True)
    s = 0
    out = [invs]
    for i in range(n):
        s += c[i]
        out.append(invs - s - i * (i + 1) // 2)
    print(*out)