概要

各時点で「これから戻す本のうち、今戻した棚番号より小さい棚に戻す本が何冊あるか」を数え、その総和を求める問題です。これは配列 \(G\) の 転倒数（inversion）を数えることと同値です。

考察

\(L_i\) は「\(i\) より後ろ（\(i+1..M\)）にある値のうち、\(G_i\) より小さいものの個数」です。つまり [ L_i = |{j \mid i G_j}| ] となり、これは \(G\) の転倒数そのものです。

素朴解が遅い理由

各 \(i\) について後ろの要素を全部見て「小さいもの」を数えると、最悪で - \(i=1\) で \(M-1\) 個 - \(i=2\) で \(M-2\) 個 - … 合計 \(O(M^2)\) になり、\(M \le 2\times 10^5\) では間に合いません。

どう解決するか

「右側にある値の出現回数」をデータ構造に持っておき、ある値 \(x\) に対して - 「\(x-1\) 以下はいくつあるか？」（= \(x\) 未満の個数） を高速に求められればよいです。そこで Fenwick Tree（BIT） を使います。

アルゴリズム

BIT に「すでに見た（= 右側にある）棚番号の個数」を保持し、\(G\) を右から左へ走査します。

• 右から左へ \(x = G_i\) を見るとき、BIT には \(G_{i+1},\dots,G_M\) が登録済み
• よって \(L_i\) は「登録済みのうち \(x\) 未満の個数」なので [ L_i = \text{BIT.sum}(x-1) ]
• その後、現在の \(x\) を BIT に追加（出現回数 +1） [ \text{BIT.add}(x, 1) ]

小さな例

\(G=[3,1,2]\) のとき（右から処理）: - 見る \(2\): 右側なし → \(<2\) は 0、追加(2) - 見る \(1\): 右側に {2} → \(<1\) は 0、追加(1) - 見る \(3\): 右側に {1,2} → \(<3\) は 2、追加(3) 合計 \(2\)（転倒は (3,1), (3,2) の2個）となります。

計算量

• 時間計算量: \(O(M\log N)\)（各要素につき BIT の加算・累積和がそれぞれ \(O(\log N)\)）
• 空間計算量: \(O(N)\)（BIT 配列）

実装のポイント

• BIT は 1-indexed で実装するのが定石なので、棚番号 \(G_i\)（\(1..N\)）をそのまま使えます。

• 「\(x\) 未満の個数」は sum(x-1) で求めます（sum(x) では「\(x\) 以下」になってしまう点に注意）。

• 答えは最大で \(M(M-1)/2\) になり得るため、言語によっては 64bit 整数が必要です（Python は自動で大丈夫）。

  ソースコード

import sys

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    G = data[2:2+M]

    fw = Fenwick(N)
    ans = 0
    for x in reversed(G):
        ans += fw.sum(x - 1)
        fw.add(x, 1)

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。