Solution 1

For a boolean value \(F\), let \([F]\) be \(1\) if \(F\) is true and \(0\) if \(F\) is false.

Let \(G_i\) be the set of \(j\) with \(B_j=i\); then \(B\)’s inversion number can be represented as:

\[\sum_{1\le i < j\le M}\sum_{x\in G_i}\sum_{y\in G_j} [x>y] \]

For \(k=0\), \(B\) coincides with \(A\); in this case, the inversion number can be found in \(O(N\log N)\) time, for example by using Fenwick Tree.

Now we will consider how to find the delta of the inversion numbers for \(k=c\) and \(k=c-1\) for each \(c=1,2,\ldots,M-1\).

Let \(B^{c-1}\) denote the sequence \(B\) for \(k=c-1\), and \(B^c\) denote that for \(k=c\).

Then, the ordering of a pair of elements in \(B^{c-1}\) and \(B^c\) changes only if the pair contains \(i\) with \(B^c_i=0\), which holds if and only if \(A_i=M-c\), which means \(i\) belongs to \(G_{M-c}\). Thus, the delta of inversion numbers of \(B^{c-1}\) and \(B^c\) can be written as \(\displaystyle C_1-C_2\), where \(C_1\) is the inversion number of an integer sequence \(X\) defined as \(X_i=[i\in G_{M-c}]\), and \(C_2\) that for \(X_i=[i\notin G_{M-c}]\).

These \(C_1\) and \(C_2\) can be represented as \(\displaystyle C_1=\sum_{i=1}^{|G_{M-i}|} (Y_i-i)\) and \(\displaystyle C_2=\sum_{i=1}^{|G_{M-i}|} \left(N-1-Y_i-(|G_{M-i}|-1-i)\right)\), where \(G_{M-i}=\lbrace Y_1,Y_2,\ldots,Y_{|G_{M-c}|}\rbrace \) \((0\le Y_1 < Y_2 < \ldots , Y_{|G_{M-c}|} \le M-1)\) (0-based indexing). Thus, \(C_1\) and \(C_2\) can be computed in \(O(|G_{M-i}|)\) time, so computing it for all \(c=1,2,\ldots,M-1\) costs a total of \(O(N)\) time.

The problem can be solved by implementing the algorithm above. The time complexity is \(O(N\log M+M)\).

Sample code (Python 3)

from atcoder import fenwicktree

n, m = map(int, input().split())
a = list(map(int, input().split()))
g = [[] for _ in range(m)]
for i in range(n):
    g[a[i]].append(i)
ans = 0
f = fenwicktree.FenwickTree(m)
for i in a:
    ans += f.sum(i + 1, m)
    f.add(i, 1)
print(ans)
for c in range(1, m):
    c1, c2 = 0, 0
    for idx, val in enumerate(g[m - c]):
        c1 += val - idx
        c2 += n - 1 - val - (len(g[m - c]) - 1 - idx)
    ans += c1 - c2
    print(ans)

---

Solution 2

Let \([x,y)\) represent the set of integers between \(x\) (inclusive) and \(y\) (exclusive).

For a fixed integer pair \((i,j)\) \((i < j)\), we consider which \(k\) satisfies \(B_i> B_j\).

[1] If \(A_i < A_j\)

The set of integers \(k\) with \(B_i> B_j\) is \([M-A_j,M-A_i)\).

[2] If \(A_i = A_j\)

No \(k\) satisfies \(B_i> B_j\).

[3] If \(A_i > A_j\)

The set of integers \(k\) with \(B_i> B_j\) is the union of \([0,M-A_i) \) and \( [M-A_j,M)\) (which are disjoint).

By using these facts and the cumulative sum trick, the problem can be solved by the following algorithm in a total of \(O(N^2+M)\) time:

• Prepare an array \(\text{ans}\) of length \((M+1)\) to store the answer. The last element is a dummy element.
• For every integer pair \((i,j)\) with \(1\le i < j\le N\), perform the following operation in order.
  • If \(A_i < A_j\), increment \(\text{ans}[M-A_j]\) by one and decrement \(\text{ans}[M-A_i]\) by one.
  • If \(A_i > A_j\), increment \(\text{ans}[0],\text{ans}[M-A_j]\) by one and decrement \(\text{ans}[M-A_i],\text{ans}[M]\) by one.
• For each \(i=1,2,\ldots,M-1\) in order, add \(\text{ans}[i-1]\) to \(\text{ans}[i]\).

Let us consider how we can improve the time complexity of this algorithm.

First, the indices of the array \(\text{ans}\) to be incremented or decremented are independent for \(i\) and \(j\). Also, for each \(i\), the number of indices \(j\) such that \(\text{ans}[M-A_i]\) is incremented equals the number of \(j\) such that \(j < i\) and \(A_i\neq A_j\), so we can prepare a array to count such \(j\) in order. Same applies to increment/decrement of \(\text{ans}[M-A_j]\).

The number of increments/decrements to \(\text{ans}[0]\) and \(\text{ans}[M]\) is the number of pairs \((i,j)\), which coincides with the inversion number of \(A\).

The problem can be solved by implementing the algorithm above. The time complexity is \(O(N\log M + M)\).

Sample code (Python)

from atcoder import fenwicktree

n, m = map(int, input().split())
a = list(map(int, input().split()))

res = 0
f = fenwicktree.FenwickTree(m)
for i in a:
    res += f.sum(i + 1, m)
    f.add(i, 1)

ans = [0] * (m + 1)
ans[0] = res
ans[m] = -res

cnt = [0] * m
for i, v in enumerate(a):
    ans[m - v] += i - cnt[v]
    cnt[v] += 1

cnt = [0] * m
for i, v in enumerate(reversed(a)):
    ans[m - v] -= i - cnt[v]
    cnt[v] += 1

for i in range(1, m + 1):
    ans[i] += ans[i - 1]

print(*ans[:-1], sep="\n")