Overview

This is a problem where you repeatedly remove books that satisfy certain conditions from a bookshelf and close the gaps, and after each operation, you need to find the number of remaining books.

Analysis

First, let’s consider a naive simulation approach using an array (list) as described in the problem statement. Deleting an element from an array and shifting elements left requires moving all elements to the right of the deleted position, which takes up to \(O(N)\) time per operation. Repeating this \(Q\) times results in an overall time complexity of \(O(QN)\), which will exceed the time limit (TLE) under the given constraints (\(N, Q \le 2 \times 10^5\)).

The key insight for solving this problem efficiently is the approach of “instead of actually moving books, managing whether a book ‘exists (1)’ or ‘does not exist (0)’ at each initial position”.

In the initial state, all positions have books, so the state is [1, 1, 1, ..., 1]. If the 2nd book from the left is removed, it becomes [1, 0, 1, ..., 1]. In this case, “the \(k\)-th book from the left currently on the shelf” can be identified as “the smallest index where the prefix sum equals exactly \(k\)”.

Thus, if we use a data structure that can efficiently perform these two operations: 1. Point update (removing a book = changing 1 to 0) 2. Prefix sum query/search (finding the position of the \(k\)-th book from the left)

we can solve the problem efficiently. Binary Indexed Tree (BIT / Fenwick Tree) or Segment Tree are suitable for this purpose.

Algorithm

Here, we explain the solution using a Binary Indexed Tree (BIT), which has a lightweight implementation and fast constant factors.

1. Initialization:

   • Prepare a BIT of length \(N\) and set 1 at all positions \(1, 2, \dots, N\).
   • Prepare an array \(D\) of book durabilities.
   • Initialize the current book count \(M\) to \(N\).

2. Query Processing: For each operation \(T_j\), perform the following steps:

   • If \(T_j > M\), no book exists at the specified position, so output \(M\) without doing anything and proceed to the next operation.
   • If \(T_j \le M\), perform a binary search on the BIT to find “the position (index) where the prefix sum equals \(T_j\)”. This is the initial position of the book currently at the \(T_j\)-th position from the left.
   • Decrease the durability \(D\) of the book at the found position by \(1\).
   • If the durability reaches \(0\), the book is removed, so decrease the value at that position in the BIT by \(1\) to update it to 0. At the same time, decrease the current book count \(M\) by \(1\).
   • Output the book count \(M\) after the operation.

Complexity

• Time complexity: \(O(N + Q \log N)\)
  • BIT initialization can be done in \(O(N)\).
  • For each query, the binary search on the BIT and value update take \(O(\log N)\). Since this is performed \(Q\) times, the total query processing time is \(O(Q \log N)\).
• Space complexity: \(O(N)\)
  • We use \(O(N)\) memory for the array managing book durabilities and the BIT array.

Implementation Notes

• Binary search on BIT: Combining a standard binary search with the BIT’s sum function would take \(O(\log^2 N)\), but by using doubling (a technique that determines bits from the highest to the lowest using powers of 2), we can directly search the BIT and find the target index in \(O(\log N)\).

• Fast I/O: In Python, when the input size is large, calling input() in a loop can be slow. By reading all input at once using sys.stdin.read().split(), we can eliminate the I/O bottleneck.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    D = [int(x) for x in input_data[2:N+2]]
    T = [int(x) for x in input_data[N+2:]]
    
    tree = [0] * (N + 1)
    for i in range(1, N + 1):
        tree[i] += 1
        nxt = i + (i & -i)
        if nxt <= N:
            tree[nxt] += tree[i]
            
    max_pow = 1
    while max_pow * 2 <= N:
        max_pow *= 2
        
    M = N
    out = []
    
    for t in T:
        if t <= M:
            idx = 0
            k = t
            step = max_pow
            while step > 0:
                next_idx = idx + step
                if next_idx <= N and tree[next_idx] < k:
                    idx = next_idx
                    k -= tree[idx]
                step //= 2
            
            idx += 1
            D[idx - 1] -= 1
            if D[idx - 1] == 0:
                M -= 1
                i = idx
                while i <= N:
                    tree[i] -= 1
                    i += i & -i
        
        out.append(str(M))
        
    print('\n'.join(out))

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.1-pro-thinking.