解法①

論理式 \(F\) に対して \([F]\) で \(F\) が真なら \(1\) 、偽なら \(0\) を表すとします。

\(G_i\) を \(B_j=i\) を満たす \(j\) の集合とすると、 \(B\) の転倒数は以下のように表されます。

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

\(k=0\) の場合の \(B\) は \(A\) と一致しており、この場合の転倒数は Fenwick Tree などを用いることで \(O(N\log N)\) 時間で求めることができます。

以下では \(c=1,2,\ldots,M-1\) に対し \(k=c\) の場合と \(k=c-1\) の場合の転倒数の差分を求めることを考えます。

\(k=c-1\) の場合の \(B\) を \(B^{c-1}\) と表記します。 \(k=c\) の場合の \(B\) も \(B^c\) と表記します。

すると、 \(B^{c-1}\) と \(B^c\) で大小関係が変わるのは \(B^c_i=0\) となる \(i\) です。これは \(A_i=M-c\) を満たす \(i\) であること、つまり \(G_{M-c}\) に属することと同値です。よって、整数列 \(X\) を \(X_i=[i\in G_{M-c}]\) と定義したときの \(X\) の転倒数を \(C_1\) 、\(X_i=[i\notin G_{M-c}]\) と定義したときの \(X\) の転倒数を \(C_2\) とすると、\(B^{c-1}\) の転倒数と \(B^c\) の転倒数の差は \(\displaystyle C_1-C_2\) と書けることが分かります。

この \(C_1,C_2\) は \(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-indexed) に対し \(\displaystyle C_1=\sum_{i=1}^{|G_{M-i}|} (Y_i-i), \) \(\displaystyle C_2=\sum_{i=1}^{|G_{M-i}|} \left(N-1-Y_i-(|G_{M-i}|-1-i)\right)\) と計算できるため、どちらも \(O(|G_{M-i}|)\) 時間で計算できます。これらを \(c=1,2,\ldots,M-1\) に対して計算しても全体で \(O(N)\) 時間となります。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log M+M)\) 時間です。

実装例(Python3)

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)

---

解法②

\([x,y)\) で \(x\) 以上 \(y\) 未満の整数の集合を表すとします。

整数の組 \((i,j)\) \((i < j)\) を一つ固定し、 \(B_i> B_j\) を満たす整数 \(k\) について考えます。

[1] \(A_i < A_j\) のとき

\(B_i> B_j\) となる \(k\) の集合は \([M-A_j,M-A_i)\) です。

[2] \(A_i = A_j\) のとき

\(B_i> B_j\) となる \(k\) は存在しません。

[3] \(A_i> A_j\) のとき

\(B_i> B_j\) となる \(k\) の集合は \([0,M-A_i) \) と \( [M-A_j,M)\) の和集合です（この \(2\) つの集合は互いに素です）。

これらの事実と imos 法を用いることで、以下のアルゴリズムにより \(k=0,1,\ldots,M-1\) に対する答えを \(O(N^2+M)\) 時間で求めることができます：

• 答えを格納する長さ \(M+1\) の配列 \(\text{ans}\) を用意する。最後の要素はダミーとする。
• \(1\le i < j\le N\) を満たす全ての整数の組 \((i,j)\) に対して以下の操作を順に行う：
  • \(A_i < A_j\) なら \(\text{ans}[M-A_j]\) に \(1\) を足し、 \(\text{ans}[M-A_i]\) から \(1\) を引く。
  • \(A_i > A_j\) なら \(\text{ans}[0],\text{ans}[M-A_j]\) に \(1\) を足し、 \(\text{ans}[M-A_i],\text{ans}[M]\) から \(1\) を引く。
• \(i=1,2,\ldots,M-1\) の順に \(\text{ans}[i]\) へ \(\text{ans}[i-1]\) を足す。

このアルゴリズムの時間計算量を改善することを考えます。

まず、imos 法を用いることにより配列 \(\text{ans}\) へ足す際のインデックスは \(i,j\) それぞれ独立になっています。また、各 \(i\) に対し \(\text{ans}[M-A_i]\) へ加算されるような \(j\) の個数は \(j < i\) かつ \(A_i\neq A_j\) を満たす \(j\) の個数と一致するので、カウンタとなる配列を用意してそのような \(j\) の個数を順に数えていけば良いです。 \(\text{ans}[M-A_j]\) への加算・減算の回数も同様です。

\(\text{ans}[0],\text{ans}[M]\) への加算・減算の回数は \(A_i>A_j\) となる \((i,j)\) の個数であり、これは \(A\) の転倒数と一致します。

以上を適切に実装することで正答することができます。計算量は \(O(N\log M + M)\) 時間です。

実装例(Python3)

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")