概要

\(M\) 冊の本を順番に棚に戻すとき、各本について「まだ戻していない本のうち、自分より小さい番号の棚に戻すべき本の冊数」を求め、その合計を計算する問題です。これは数列の転倒数（inversion count）を求める問題に帰着できます。

考察

\(L_i\) の意味を整理する

\(L_i\) は「\(i\) より後に戻す本のうち、棚番号が \(G_i\) 未満であるものの冊数」です。式で書くと：

\[L_i = \#\{j \mid i < j \leq M, \ G_j < G_i\}\]

合計の言い換え

\(L_1 + L_2 + \cdots + L_M\) を全体で見ると、これはすべてのペア \((i, j)\)（\(i < j\)）について \(G_i > G_j\) となるペアの数を数えていることになります。

\[\sum_{i=1}^{M} L_i = \#\{(i, j) \mid 1 \leq i < j \leq M, \ G_i > G_j\}\]

これはまさに数列 \(G_1, G_2, \ldots, G_M\) の転倒数（inversion count）です。

具体例

例えば \(G = [3, 1, 2]\) の場合： - \(L_1\)：後ろの \([1, 2]\) のうち \(3\) 未満のもの → \(1, 2\) の2冊 → \(L_1 = 2\) - \(L_2\)：後ろの \([2]\) のうち \(1\) 未満のもの → 0冊 → \(L_2 = 0\) - \(L_3\)：後ろに本がない → \(L_3 = 0\) - 合計：\(2 + 0 + 0 = 2\)（転倒ペアは \((3,1)\) と \((3,2)\)）

素朴なアプローチの問題点

全ペアを調べると \(O(M^2)\) となり、\(M\) が最大 \(2 \times 10^5\) のため間に合いません。

アルゴリズム

Binary Indexed Tree（BIT / Fenwick Tree） を用いて転倒数を効率的に求めます。

手順：右から左に走査する

1. BIT を用意し、すべて \(0\) で初期化する。BIT の各位置は「棚番号 \(k\) の本がこれまで何冊挿入されたか」を管理する。
2. 配列 \(G\) を右端（\(i = M-1\)）から左端（\(i = 0\)）へ順に処理する。
3. 各 \(G[i]\) に対して：
   • query(G[i] - 1)：BIT に既に挿入されている値のうち \(G[i]\) 未満のものの個数を取得する。これが \(L_i\) に相当する（既に挿入済み = \(i\) より後ろの要素）。
   • 答えにこの値を加算する。
   • update(G[i])：\(G[i]\) を BIT に挿入する。

右から左に見ているため、BIT に入っている要素は「現在の位置より右側の要素」であり、query(G[i] - 1) で「右側にあって \(G[i]\) より小さい値の個数」、つまり \(L_i\) が正しく求まります。

計算量

• 時間計算量: \(O(M \log N)\)（各要素について BIT の更新・クエリが \(O(\log N)\)）
• 空間計算量: \(O(N + M)\)（BIT のサイズ \(N\) と入力配列のサイズ \(M\)）

実装のポイント

• BIT の query は前方累積和（位置 \(1\) から \(pos\) まで）を返すので、\(G[i]\) 未満の個数を得るには query(G[i] - 1) とする。\(G[i] = 1\) のときは query(0) = 0 となるため、場合分けまたは G[i] > 1 のチェックを入れると安全。

• Python では入力が大きい場合 sys.stdin.buffer.read() でまとめて読むと高速化できる。

• BIT のインデックスは \(1\)-indexed で管理する（\(0\) を含めるとビット演算がうまく動かない）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    G = [int(input_data[idx + i]) for i in range(M)]
    idx += M

    # BIT (Binary Indexed Tree) for counting
    # We need suffix counts: for each i, count how many j > i have G[j] < G[i]
    # Sum of L_i = sum over i of (number of j > i with G[j] < G[i])
    # This equals: sum over i of (number of j < i with G[j] > G[i]) ... no, that's inversions in different direction
    # 
    # Actually L_i = number of j in {i+1,...,M} with G[j] < G[i]
    # So total = sum_{i<j} [G[j] < G[i]]
    # This is the number of pairs (i,j) with i < j and G[i] > G[j], i.e., the number of inversions.
    
    # Count inversions using BIT
    # Process from right to left, maintaining counts of values seen so far
    # For each G[i], query prefix sum [1, G[i]-1] to get count of elements already inserted that are < G[i]
    
    bit = [0] * (N + 1)
    
    def update(pos):
        while pos <= N:
            bit[pos] += 1
            pos += pos & (-pos)
    
    def query(pos):
        s = 0
        while pos > 0:
            s += bit[pos]
            pos -= pos & (-pos)
        return s
    
    ans = 0
    # Process from right to left
    for i in range(M - 1, -1, -1):
        g = G[i]
        # Count elements already in BIT with value < g
        if g > 1:
            ans += query(g - 1)
        update(g)
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。