Overview

Books are removed partway through, causing “the \(T\)-th book from the left” to change each time. We need to efficiently simulate the operation of reducing the durability of a specified book and deleting it when it reaches 0.

Analysis

The difficulty of this problem is that every time a book is deleted, the books to its right shift left, so which book is “the \(T\)-th from the left” changes dynamically.

Why a Naive Approach Fails

For example, if we manage the bookshelf with an array or list and for each operation: - Directly access the \(T\)-th book and reduce its durability - If it reaches 0, delete it and shift elements

Then each deletion requires up to \(O(N)\) shifting work.

In the worst case, if every one of the \(Q\) operations causes a deletion,
this becomes \(O(NQ)\) (up to \(2\times 10^5 \times 2\times 10^5\)), which is far too slow.

Key Insight

• We can think of each book’s “original position (1 to \(N\))” as fixed
• What changes due to deletions is “the ordering when only surviving books are packed to the left (= the \(k\)-th book)”

In other words, what we need each time is: - Among the currently surviving books, which original position does the \(T\)-th one correspond to?

The classic technique for finding “the position of the \(k\)-th 1” is a BIT (Fenwick Tree).

Algorithm

Data Structures

• Array D[i]: durability of the book at original position \(i\) (values are kept even after deletion)
• BIT: stores 1 at each position \(i\) if the book exists, 0 if it has been removed
  • The prefix sum of the BIT tells us “how many books are alive from the beginning”
  • Furthermore, using the BIT we can find “the smallest position where the prefix sum reaches \(k\)” = the original position of the \(k\)-th surviving book (order statistics)

Processing Each Operation (\(T\))

1. Let alive be the current number of remaining books
2. If \(T > alive\), nothing happens (just output)
3. Otherwise:
   • Use the BIT to find the original index idx of “the \(T\)-th surviving book” (kth(T))
   • D[idx] -= 1
   • If D[idx] == 0, delete it:
     • Add -1 to the corresponding BIT position, changing 1→0
     • alive -= 1
4. Output alive

Concrete Example (Illustration)

When original positions are 1..5 and the existence flags are [1,1,1,1,1], deleting the 3rd book makes
the existence flags [1,1,0,1,1].
Next, “the 3rd from the left” is the position where the 3rd 1 appears in the existence flags = original position 4.
We efficiently find this using the BIT’s kth function.

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  • BIT initialization (fast construction with all 1s): \(O(N)\)
  • Each query has at most one kth and one add: \(O(\log N)\)
• Space complexity: \(O(N)\) (durability array + BIT)

Implementation Notes

• BIT is 1-indexed, so be careful about conversion with the 0-indexed array D (e.g., subtracting 1 from the return value of kth).

• Implementing kth(k) with binary lifting on the BIT achieves \(O(\log N)\).

• By maintaining the remaining count alive as a separate variable, the “\(T > M\)” check can be done in \(O(1)\).

• Since the initial state is all 1s, using something like build_ones() to construct the all-1s BIT in \(O(N)\) is fast (sequential add calls would take \(O(N\log N)\)).

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.