概要

本を置くたびに「まだ空いている棚の中で、指定位置 \(S_i\) が左から何番目か」を求める問題です。空き状況が逐次変わるため、動的に「左側の空き数」を数えます。

考察

\(i\) 冊目を置く直前に、空いている収納スペースを左から数えるときの \(S_i\) の順位 \(P_i\) は、

• 「\(1\) から \(S_i\) までの範囲に空きがいくつあるか」

と同じです。なぜなら、\(S_i\) 自身もまだ空いていて、左から数えた順位は「自分より左（含む）の空き数」に一致するからです。

素朴な方法の問題点

各ステップで - \(1\) から \(S_i\) までを直接走査して空きを数える

と、1 回が最大 \(O(N)\) かかり、全体で \(O(NM)\) になり得ます。制約は \(N, M \le 2 \times 10^5\) なので、これは間に合いません。

解決の方向性

必要なのは次の 2 操作を高速に行うことです：

1. 区間 \([1, S_i]\) の「空き数」を求める（前からの累積和）
2. \(S_i\) を埋める（空き \(1\) を \(0\) に更新）

これをどちらも \(O(\log N)\) で処理できれば全体で高速化できます。

アルゴリズム

ここでは Fenwick Tree（Binary Indexed Tree, BIT） を使います。

データの持ち方

• 各位置 \(k\) が空いているなら値を \(1\)、埋まっているなら \(0\) とする配列を考える。
• 初期状態はすべて空なので、全要素が \(1\)。

このとき、 - \(P_i = \sum_{k=1}^{S_i} a_k\)（\(a_k\) は空きなら 1）

となります。

処理手順

各 \(S_i\) について次を行います：

1. fw.sum(S_i) を計算する
   
   • これは「\(1\) から \(S_i\) までの空き数」＝求める \(P_i\)
2. fw.add(S_i, -1) で \(S_i\) の値を \(1 \to 0\) に更新
   
   • 本を置いて埋まったことを反映

具体例

例えば \(N=5\)、置く位置が \(S=[3,1,5]\) のとき：

• 初期：空き状態 \([1,1,1,1,1]\)
• \(S_1=3\)
  
  • \(P_1 = \text{sum}(3)=3\)（1〜3 は全部空き）
    
  • 更新後：\([1,1,0,1,1]\)
• \(S_2=1\)
  
  • \(P_2 = \text{sum}(1)=1\)
    
  • 更新後：\([0,1,0,1,1]\)
• \(S_3=5\)
  
  • \(P_3 = \text{sum}(5)=3\)（空きは 2,4,5 の3つ）
    

このように、常に「前からの空き数」を数えれば順位が出ます。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  
  • 初期化後、各クエリ（sum と add）がそれぞれ \(O(\log N)\)
• 空間計算量: \(O(N)\)
  
  • Fenwick Tree の配列を保持

実装のポイント

• Fenwick Tree は通常 1-indexed で実装するので、棚番号 \(1 \sim N\) をそのまま使えて都合が良いです。

• 初期状態が「全て 1」なので、コードでは Fenwick を全 1 で構築しています（__init__ 内で \(O(N)\) ビルド）。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み、出力も最後にまとめて書くと高速です。

  ソースコード

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
        # build with all ones in O(n)
        for i in range(1, n + 1):
            self.bit[i] += 1
            j = i + (i & -i)
            if j <= n:
                self.bit[j] += self.bit[i]

    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()))
    n, m = data[0], data[1]
    s_list = data[2:2 + m]

    fw = Fenwick(n)
    out = []
    for s in s_list:
        out.append(str(fw.sum(s)))
        fw.add(s, -1)

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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