概要

本を配置する際に、その収納スペースが「現在空いているスペースの中で左から何番目か」を効率的に求める問題です。Binary Indexed Tree（BIT）を使って、動的に変化する空きスペースの数を高速に管理します。

考察

問題の言い換え

収納スペース \(S_i\) が「空いているスペースの中で左から何番目か」は、言い換えると「位置 \(1\) から \(S_i\) までの間にある空きスペースの個数」と同じです。

例えば、\(N = 5\) で収納スペース \(1, 3\) が既に使用済みの場合： - 空いているスペース: \(2, 4, 5\)（左から1番目, 2番目, 3番目） - \(S_i = 4\) のとき、位置 \(1\) から \(4\) までの空きスペースは \(2, 4\) の2つ → 答えは \(2\)

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

各本を配置するたびに、位置 \(1\) から \(S_i\) までの空きスペースを数えると、1回あたり最大 \(O(N)\) かかります。これを \(M\) 回繰り返すと \(O(NM)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合、最大 \(4 \times 10^{10}\) 回の操作となりTLEします。

解決策

「区間の和を高速に求める」「1点の値を更新する」という2つの操作を効率的に行えるデータ構造として、Binary Indexed Tree（BIT、Fenwick Tree とも呼ばれる） を使います。

アルゴリズム

1. 初期化: 長さ \(N\) のBITを用意し、各位置 \(i\)（\(1 \leq i \leq N\)）に値 \(1\) を設定する。これは「位置 \(i\) が空いている」ことを表す。

2. 各本の配置（\(i = 1, 2, \ldots, M\)）:

   • クエリ: BITで区間 \([1, S_i]\) の和を求める。これが「空いているスペースの中で \(S_i\) は左から何番目か」の答え \(P_i\)。
   • 更新: 位置 \(S_i\) の値を \(-1\) して \(0\) にする（使用済みにする）。

具体例（\(N = 5\), \(M = 3\), \(S = [3, 1, 4]\)）

操作	空きスペース	\(S_i\)	\([1, S_i]\) の空き数	答え \(P_i\)
初期	1,2,3,4,5	-	-	-
1冊目	1,2,3,4,5	3	3	3
2冊目	1,2,4,5	1	1	1
3冊目	2,4,5	4	2	2

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 初期化: \(N\) 回の更新、各 \(O(\log N)\) → \(O(N \log N)\)
  • 各本の配置: \(M\) 回のクエリと更新、各 \(O(\log N)\) → \(O(M \log N)\)
• 空間計算量: \(O(N)\)
  • BITの配列サイズ

実装のポイント

1. BITの1-indexed: BITは通常1-indexedで実装します。収納スペースの番号も1から始まるので相性が良いです。

2. 更新の方向:

   • update(i, delta): 位置 \(i\) に delta を加算。内部では i += i & (-i) で上位ノードへ伝播。
   • query(i): 位置 \(1\) から \(i\) までの和を求める。i -= i & (-i) で下位ノードを辿る。

3. 空きから使用済みへの変更: 初期値 \(1\)（空き）から \(0\)（使用済み）にするには、update(s, -1) を呼び出します。

   ソースコード

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    
    # BITを使って空いているスペースを管理
    # 初期状態では全てのスペースが空いている（各位置に1を設定）
    bit = BinaryIndexedTree(N)
    for i in range(1, N + 1):
        bit.update(i, 1)
    
    results = []
    for s in S:
        # s番目の収納スペースが、空いているスペースの中で左から何番目かを求める
        # これは1からsまでの区間の和（空いているスペースの数）
        pos = bit.query(s)
        results.append(pos)
        # s番目のスペースを使用済みにする
        bit.update(s, -1)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

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