概要

本が途中で取り除かれて「左から \(T\) 番目」が毎回変化する状況で、指定された本の耐久値を減らし、0 になれば削除する操作を高速にシミュレーションします。

考察

この問題の難しさは、本が削除されるたびに右側の本が左へ詰められ、「左から \(T\) 番目の本」がどれかが動的に変わる点です。

素朴な方法がダメな理由

例えば配列やリストで本棚を管理し、操作ごとに - \(T\) 番目の本を直接参照して耐久値を減らす - 0 になったら削除して詰める（要素のシフト） とすると、削除が起きるたびに最大 \(O(N)\) の詰め作業が発生します。

最悪の場合、\(Q\) 回の操作で毎回削除が起きると
\(O(NQ)\)（最大で \(2\times 10^5 \times 2\times 10^5\)）となり、到底間に合いません。

重要な気づき

• 本の「元の位置（1〜\(N\)）」は固定で考えてよい
  
• 削除によって変わるのは「生きている本だけを左詰めしたときの順番（= \(k\) 番目）」
  つまり、必要なのは毎回
• 現在生きている本のうち \(T\) 番目が、元の何番目か を素早く求めることです。

この「\(k\) 番目の 1 の位置」を求める典型手法が BIT（Fenwick Tree） です。

アルゴリズム

データ構造

• 配列 D[i]：元の位置 \(i\) の本の耐久値（削除されても値は持っておく）
• BIT：各位置 \(i\) に「その本が存在するなら 1、消えたら 0」を入れる
  
  • BIT の prefix sum により「先頭から何冊生きているか」が分かる
  • さらに BIT の機能として「累積和が \(k\) 以上になる最小の位置」= \(k\) 番目に生きている本の元位置 が求められる（order statistics）

各操作（\(T\)）の処理

1. 現在の残冊数を alive とする
2. もし \(T > alive\) なら何も起こらない（出力だけ）
3. そうでなければ
   • BIT で「生きている本のうち \(T\) 番目」の元の添字 idx を求める（kth(T)）
   • D[idx] -= 1
   • D[idx] == 0 なら削除：
     • BIT の該当位置に -1 を加えて 1→0 にする
     • alive -= 1
4. alive を出力

具体例（イメージ）

元の位置が 1..5、存在フラグが [1,1,1,1,1] のときに 3 番目を削除すると
存在フラグは [1,1,0,1,1] になります。
次に「左から 3 番目」は、存在フラグで 1 が 3 個目に現れる位置＝元の位置 4 です。
これを BIT の kth で高速に求めます。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
  
  • BIT 初期化（ここでは 1 埋めを高速に構築）: \(O(N)\)
    
  • 各クエリで kth と add が最大 1 回ずつ: \(O(\log N)\)
• 空間計算量: \(O(N)\)（耐久値配列 + BIT）

実装のポイント

• BIT は 1-indexed なので、配列 D（0-indexed）との変換に注意します（kth の戻り値から -1 するなど）。

• kth(k) は BIT 上の二分探索（binary lifting）で実装すると \(O(\log N)\) で求まります。

• 残冊数 alive を別変数で持つことで、「\(T > M\)」判定を \(O(1)\) でできます。

• 初期状態が全て 1 なので、build_ones() のように 全要素 1 の BIT を \(O(N)\) 構築すると高速です（逐次 add だと \(O(N\log N)\)）。

  ソースコード

import sys

class BIT:
    __slots__ = ("n", "bit")
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)

    def build_ones(self):
        b = self.bit
        n = self.n
        for i in range(1, n + 1):
            b[i] += 1
            j = i + (i & -i)
            if j <= n:
                b[j] += b[i]

    def add(self, i: int, v: int):
        b = self.bit
        n = self.n
        while i <= n:
            b[i] += v
            i += i & -i

    def kth(self, k: int) -> int:
        b = self.bit
        n = self.n
        idx = 0
        step = 1 << (n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= n and b[nxt] < k:
                k -= b[nxt]
                idx = nxt
            step >>= 1
        return idx + 1

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, Q = data[0], data[1]
    D = data[2:2 + N]
    T = data[2 + N:]

    bit = BIT(N)
    bit.build_ones()
    alive = N

    out = []
    for t in T:
        if t <= alive:
            idx = bit.kth(t) - 1
            D[idx] -= 1
            if D[idx] == 0:
                bit.add(idx + 1, -1)
                alive -= 1
        out.append(str(alive))

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

if __name__ == "__main__":
    main()

---

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