取り除かれた本を詰めないことで、「残っている本のうち左から \(T\) 番目は元々何番目の本か？」を高速に判定することができればよいです。

「元々 \(i\) 番目の本がまだ本棚に残っていれば \(1\) 、取り除かれていれば \(0\) 」となる配列 \(F_i\) を考えます。このとき元々 \(i\) 番目の本は、いま本棚にある本のうち左から \(\sum_{j=1}^{i}F_i\) 番目となります。よって逆にいま本棚になる本のうち左から \(x\)番目の本が元々何番目であるかは、 \(F\) の累積和の二分探索により求めることができます。

\(1\) 回の操作では \(F\) の高々 \(1\) 箇所のが更新されるため、 1点更新・区間和取得が高速に行えるデータ構造で \(F\) を管理すればよく、セグメントツリーにより実現できます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;

int e(){return 0;}
int op(int x, int y){return x + y;}

int main(){
  int n, q;
  cin >> n >> q;
  vector<int>d(n);
  for(int i=0; i<n; i++) cin >> d[i];

  atcoder::segtree<int, op, e>seg(vector<int>(n, 1));
  for(int i=0; i<q; i++){
    int t;
    cin >> t;
    auto f = [&](int x){return x < t;};
    int r = seg.max_right(0, f);
    if(r != n){
      d[r]--;
      if(d[r] == 0){
        seg.set(r, 0);
      }
    }
    cout << seg.all_prod() << endl;
  }
}

実装例 (Python)

from atcoder.segtree import SegTree
from operator import add

N, Q = map(int, input().split())
D = list(map(int, input().split()))

seg = SegTree(add, 0, [1]*N)
for _ in range(Q):
  T = int(input())
  def f(x):
    return x < T
  r = seg.max_right(0, f)
  if r != N:
    D[r] -= 1
    if D[r] == 0:
      seg.set(r, 0)
  print(seg.all_prod())