Overview

This problem requires efficiently processing operations that decrease the durability of “the book currently at position T from the left” on a bookshelf, removing it when its durability reaches 0. Since books are packed together after removal, we need to quickly determine which original book corresponds to “the current k-th position.”

Analysis

Issues with a Naive Approach

The most intuitive method is to manage the bookshelf with an array and delete elements each time a book is removed. However, deleting an element from the middle of an array takes \(O(N)\), and with \(Q\) operations, the total complexity becomes \(O(NQ)\). Since \(N, Q\) can be up to \(2 \times 10^5\), this results in approximately \(4 \times 10^{10}\) operations, which will TLE.

Key Insight

The operation of removing a book and packing the remaining ones can be reduced to “finding the k-th book among the currently remaining books from the left.” This is the classic problem of “quickly finding the k-th element,” which can be solved using a k-th element query with a Binary Indexed Tree (BIT / Fenwick Tree).

Specifically, for each original position \(i\) of a book, we maintain a value in the BIT: 1 if the book is still present, 0 if it has been removed. Then, by finding the minimum position where the prefix sum in the BIT reaches \(k\), we can determine “the original position of the current k-th book” in \(O(\log N)\).

Algorithm

1. Initialization: Create a BIT of length \(N\) and set all positions to 1. Set remaining = N.
2. For each query \(T_j\):
   • If \(T_j > \text{remaining}\), do nothing.
   • Otherwise, find the position of the \(T_j\)-th 1 in the BIT (= the original position \(p\) of the book) using binary lifting.
   • Decrease \(D[p]\) by 1.
   • If \(D[p] = 0\), update position \(p\) in the BIT to 0 and decrease remaining by 1.
   • Output remaining.

Finding the k-th element on the BIT (binary lifting)

Using the structure of the BIT, we find the minimum position where the prefix sum reaches \(k\) in \(O(\log N)\). We try powers of 2 from largest to smallest, advancing if the prefix sum is still less than \(k\) — a greedy approach.

Example: With \(N=5\), \(D = [2, 1, 3, 1, 2]\) and \(T=3\), the position of the 3rd 1 in the BIT is original position 3. If the book at position 2 has already been removed, then the 3rd element in the BIT corresponds to original position 4.

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • BIT initialization: \(O(N \log N)\)
  • Each query: \(O(\log N)\) for k-th element search, \(O(\log N)\) for BIT update
• Space complexity: \(O(N)\)
  • BIT array and durability array

Implementation Notes

• It is standard practice to manage the BIT as 1-indexed. Original book positions are also treated as 1-indexed, and since the durability array \(D\) is 0-indexed, we access it with D[pos - 1].

• In the find_kth function, binary lifting starts from the smallest power of 2 that is at least the size of the BIT. This is faster than a standard binary search due to smaller constant factors.

• Input is read all at once using stdin.buffer.read(), and output is accumulated in an array and printed all at once at the end to reduce I/O overhead.

  Source Code

import sys
from sys import stdin

def main():
    input = stdin.buffer.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    Q = int(input[idx]); idx += 1
    
    D = [0] * N
    for i in range(N):
        D[i] = int(input[idx]); idx += 1
    
    # BIT (Fenwick Tree) to track which positions still have books
    # We store 1 for each position that still has a book
    # To find the k-th book, we do a binary search on the BIT
    
    size = N + 1
    bit = [0] * size
    
    def update(i, delta):
        # 1-indexed
        while i < size:
            bit[i] += delta
            i += i & (-i)
    
    def query(i):
        # prefix sum [1..i]
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    def find_kth(k):
        # Find the smallest position p such that prefix_sum(p) >= k
        # Using binary lifting on BIT
        pos = 0
        r = 1
        while r < size:
            r <<= 1
        r >>= 1
        cur_sum = 0
        while r > 0:
            if pos + r < size and cur_sum + bit[pos + r] < k:
                pos += r
                cur_sum += bit[pos]
            r >>= 1
        return pos + 1
    
    # Initialize BIT: all N books present
    for i in range(1, N + 1):
        update(i, 1)
    
    remaining = N
    
    out = []
    for _ in range(Q):
        T = int(input[idx]); idx += 1
        if T > remaining:
            out.append(str(remaining))
        else:
            # Find the T-th remaining book's original position
            pos = find_kth(T)  # 1-indexed original position
            D[pos - 1] -= 1
            if D[pos - 1] == 0:
                update(pos, -1)
                remaining -= 1
            out.append(str(remaining))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.