Submission #63549603

---

Source Code Expand

N, M = map(int, input().split())
A = list(map(int, input().split()))
s = M + 1
bit = [0] * s


def update(i, v):
    while i < s:
        bit[i] += v
        i += i & -i


def query(i):
    res = 0
    while i:
        res += bit[i]
        i -= i & -i
    return res


inv = 0
for i, a in enumerate(A):
    q = query(a + 1)
    inv += i - q
    update(a + 1, 1)

res = [0] * M
res[0] = inv
d = [0] * (M + 1)
for i, a in enumerate(A):
    if a:
        k = M - a
        d[k] += i - (N - i - 1)

cur = inv
for k in range(1, M):
    cur += d[k]
    res[k] = cur

for x in res:
    print(x)

Submission Info

Judge Result