概要

本を棚に戻す順番ごとに、まだ戻していない本のうち戻す棚の番号が現在の本の棚番号より小さいものの個数を記録し、その合計値を求める問題です。

考察

各本を戻すタイミングで、それ以降に戻す予定の本のうち棚番号が現在の本より小さいものの個数（\(L_i\)）を求める必要があります。素朴な方法では、各本についてそれ以降のすべての本を調べると\(O(M^2)\)の計算量となり、\(M\)が最大\(2 \times 10^5\)なので実行時間制限に間に合いません。

効率的に解くためには、以下の観察が重要です： - 本を処理する順序を後ろから前に向かって処理する - 各棚番号の出現回数を効率的に管理する - 範囲クエリを高速に処理できるデータ構造（Fenwick Tree）を使用する

アルゴリズム

1. 本を処理する順序を後ろから前に向かって処理します（\(i = M-1, M-2, ..., 0\)）
2. Fenwick Tree（Binary Indexed Tree）を使用して、各棚番号の出現回数を管理します
3. 各本\(i\)について：
   • 現在の棚番号\(g_i\)より小さい棚番号（\(1\)から\(g_i-1\)まで）の出現回数の合計をFenwick Treeで取得
   • その値を合計値に加算
   • 現在の棚番号\(g_i\)の出現回数をFenwick Treeで1増加
4. 最終的に得られた合計値を出力

後ろから処理することで、各本を処理する時点でFenwick Treeには「すでに処理した本」（元の順序では後の本）の情報のみが記録されており、求めたい「それ以降の本」の情報が正しく管理できます。

計算量

• 時間計算量: \(O(M \log N)\)
  • 各本の処理でFenwick Treeの更新とクエリ処理に\(O(\log N)\)かかる
  • 本の数\(M\)回処理する
• 空間計算量: \(O(N)\)
  • Fenwick Treeのサイズが棚の数\(N\)に比例する

実装のポイント

• Fenwick Treeの実装では、インデックスが1から始まることに注意

• クエリ処理時には\(g_i > 1\)の場合のみ処理を行う（\(g_i = 1\)のときは\(g_i-1=0\)となりクエリ範囲外）

• 入力値の読み込みを効率的に行うためsys.stdin.read()を使用

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    G = list(map(int, data[2:2+m]))
    
    fenwick = [0] * (n + 2)
    
    def update(index, delta):
        while index <= n:
            fenwick[index] += delta
            index += index & -index
            
    def query(index):
        s = 0
        while index > 0:
            s += fenwick[index]
            index -= index & -index
        return s
    
    count = [0] * (n + 1)
    total = 0
    
    for i in range(m - 1, -1, -1):
        g = G[i]
        if g > 1:
            total += query(g - 1)
        update(g, 1)
        
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。