Overview

Each time a book is placed, we need to determine “among the still-empty shelves, what is the position of the specified location \(S_i\) counting from the left?” Since the vacancy status changes with each operation, we dynamically count the “number of empty slots to the left.”

Analysis

Just before placing the \(i\)-th book, the rank \(P_i\) of \(S_i\) when counting empty storage spaces from the left is equivalent to:

• “How many empty spaces are there in the range from \(1\) to \(S_i\)?”

This is because \(S_i\) itself is still empty at that point, and its rank counted from the left equals “the number of empty slots to its left (inclusive).”

Problem with the Naive Approach

At each step, if we: - Directly scan from \(1\) to \(S_i\) to count empty spaces

then each step takes up to \(O(N)\), resulting in \(O(NM)\) overall. Given the constraints \(N, M \le 2 \times 10^5\), this is too slow.

Direction for a Solution

We need to perform the following two operations efficiently:

1. Find the “number of empty spaces” in the interval \([1, S_i]\) (prefix sum)
2. Fill \(S_i\) (update the vacancy from \(1\) to \(0\))

If both operations can be processed in \(O(\log N)\), the overall solution becomes fast enough.

Algorithm

Here we use a Fenwick Tree (Binary Indexed Tree, BIT).

Data Representation

• Consider an array where each position \(k\) has value \(1\) if it is empty and \(0\) if it is occupied.
• In the initial state, all positions are empty, so all elements are \(1\).

Then, - \(P_i = \sum_{k=1}^{S_i} a_k\) (where \(a_k\) is 1 if empty)

Procedure

For each \(S_i\), perform the following:

1. Compute fw.sum(S_i)
   • This is “the number of empty spaces from \(1\) to \(S_i\)” = the desired \(P_i\)
2. Execute fw.add(S_i, -1) to update the value at \(S_i\) from \(1 \to 0\)
   • This reflects that a book has been placed and the space is now occupied

Concrete Example

For example, with \(N=5\) and placement positions \(S=[3,1,5]\):

• Initial: vacancy state \([1,1,1,1,1]\)
• \(S_1=3\)
  • \(P_1 = \text{sum}(3)=3\) (positions 1–3 are all empty)
  • After update: \([1,1,0,1,1]\)
• \(S_2=1\)
  • \(P_2 = \text{sum}(1)=1\)
  • After update: \([0,1,0,1,1]\)
• \(S_3=5\)
  • \(P_3 = \text{sum}(5)=3\) (the 3 empty positions are 2, 4, 5)

In this way, by always counting “the number of empty spaces from the front,” we obtain the rank.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  • After initialization, each query (sum and add) takes \(O(\log N)\)
• Space complexity: \(O(N)\)
  • For storing the Fenwick Tree array

Implementation Notes

• Fenwick Trees are typically implemented as 1-indexed, so shelf numbers \(1 \sim N\) can be used directly, which is convenient.

• Since the initial state is “all 1s,” the code builds the Fenwick Tree with all 1s (\(O(N)\) build inside __init__).

• Because the input can be large, reading all at once with sys.stdin.buffer.read() and writing the output all at once at the end improves speed.

  Source Code

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
        # build with all ones in O(n)
        for i in range(1, n + 1):
            self.bit[i] += 1
            j = i + (i & -i)
            if j <= n:
                self.bit[j] += self.bit[i]

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

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    s_list = data[2:2 + m]

    fw = Fenwick(n)
    out = []
    for s in s_list:
        out.append(str(fw.sum(s)))
        fw.add(s, -1)

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.