概要

\(N\) 個の並んだ収納スペースに \(M\) 冊の本を順番に置いていく際、各本を置く直前において、その収納スペースが「空いているスペースの中で左から何番目か」を求める問題です。

考察

素朴な方法とその限界

各本を置くごとに、現在の空き状況をリストなどで管理し、左から数える方法が思いつきます。 しかし、この方法では \(i\) 番目の本を置く際に最大で \(O(N)\) の時間がかかります。本は \(M\) 冊あるため、全体の計算量は \(O(NM)\) となり、制約の \(N, M \leq 2 \times 10^5\) では実行時間制限（通常 2秒程度）に間に合いません。

効率的な管理

「空いているスペースの中で左から何番目か」という問いは、以下のように言い換えることができます。 - 各収納スペースについて、空いていれば 1、埋まっていれば 0 という値を割り当てる。 - 収納スペース \(S_i\) が左から何番目かは、\(1\) 番目から \(S_i\) 番目までの値の合計（累積和）に等しい。 - 本を置いた後は、そのスペースの値を 1 から 0 に更新する。

このように、「値を更新する」操作と「ある範囲の合計（累積和）を求める」操作を高速に行う必要がある場合、Binary Indexed Tree (BIT / フェニック木) というデータ構造が非常に有効です。

アルゴリズム

Binary Indexed Tree (BIT) の利用

BIT を使うと、以下の操作をそれぞれ \(O(\log N)\) で行うことができます。 1. 加算: 指定した要素に値を加える（今回は 1 を 0 にするため、-1 を加算する）。 2. 合計: \(1\) 番目から \(k\) 番目までの要素の合計を求める。

手順

1. 初期化: \(N\) 個の要素すべてを 1（空き状態）とし、それに基づいて BIT を構築します。
2. 各本の処理: \(i = 1, 2, \ldots, M\) の順に以下を行います。
   • BIT を用いて、\(1\) から \(S_i\) までの累積和を求めます。これが答え \(P_i\) です。
   • 収納スペース \(S_i\) は埋まるため、BIT の \(S_i\) 番目の要素に -1 を加算して更新します。
3. 出力: 求めた \(P_i\) を順に出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • BIT の初期構築に \(O(N \log N)\)（あるいは工夫すれば \(O(N)\)）、\(M\) 回のクエリと更新にそれぞれ \(O(\log N)\) かかるため、十分に高速です。
• 空間計算量: \(O(N)\)
  • 長さ \(N\) の BIT 配列を保持するために必要です。

実装のポイント

• BIT のインデックス: BIT は通常 1-indexed で実装されます。問題文の収納スペースの番号も \(1\) から \(N\) なので、そのまま扱うことができます。

• 高速な入出力: \(N, M\) が大きいため、Python の場合は sys.stdin.read().split() や sys.stdout.write() を使うことで、入出力のボトルネックを解消できます。

• BIT の初期化: 1つずつ add 操作を行う代わりに、コード内の bit[i] = i & -i のような記述（累積和の性質を利用した一括初期化）を用いると、構築を \(O(N)\) で行うことができ、より効率的です。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白で分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 収納スペースの総数 N と、配置する本の冊数 M を取得します。
    N = int(input_data[0])
    M = int(input_data[1])
    # 各本を配置する収納スペース番号 S_i を取得します。
    S = [int(x) for x in input_data[2:]]
    
    # Binary Indexed Tree (BIT) を用いて、空いている収納スペースを管理します。
    # bit[i] は、i 番目の収納スペースが空いているか (1) または埋まっているか (0) の累積和を保持します。
    # 初期状態ではすべてのスペースが空いているため、各要素を 1 で初期化した BIT を構築します。
    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] = i & -i
        
    results = []
    for s_val in S:
        # 現在の収納スペース s_val が、空いているスペースの中で左から何番目か（1からs_valまでの累積和）を求めます。
        count = 0
        idx = s_val
        while idx > 0:
            count += bit[idx]
            idx &= idx - 1  # BITのクエリ操作：上位のノードへ移動
        results.append(str(count))
        
        # 本を配置したため、収納スペース s_val を「空いていない (0)」状態に更新します。
        # 具体的には、BIT の s_val 番目の値を -1 します。
        idx = s_val
        while idx <= N:
            bit[idx] -= 1
            idx += idx & (-idx)  # BITの更新操作：影響を受けるノードへ移動
            
    # 全ての結果をまとめて出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。