Overview

This problem requires efficiently determining, when placing a book, “what position from the left is this storage space among the currently available spaces.” We use a Binary Indexed Tree (BIT) to efficiently manage the dynamically changing count of available spaces.

Analysis

Rephrasing the Problem

The statement that storage space \(S_i\) is “the \(S_i\)-th space from the left among available spaces” is equivalent to “the number of available spaces between positions \(1\) and \(S_i\).”

For example, if \(N = 5\) and storage spaces \(1, 3\) are already occupied: - Available spaces: \(2, 4, 5\) (1st, 2nd, 3rd from the left) - When \(S_i = 4\), the available spaces from position \(1\) to \(4\) are \(2, 4\) — two spaces → the answer is \(2\)

Issues with a Naive Approach

If we count the available spaces from position \(1\) to \(S_i\) each time we place a book, it takes up to \(O(N)\) per operation. Repeating this \(M\) times gives \(O(NM)\), and when \(N, M\) are up to \(2 \times 10^5\), this results in up to \(4 \times 10^{10}\) operations, causing TLE.

Solution

We use a Binary Indexed Tree (BIT, also known as a Fenwick Tree) as a data structure that can efficiently perform two operations: “compute the sum over a range” and “update the value at a single point.”

Algorithm

1. Initialization: Prepare a BIT of length \(N\) and set the value \(1\) at each position \(i\) (\(1 \leq i \leq N\)). This represents “position \(i\) is available.”

2. Placing each book (\(i = 1, 2, \ldots, M\)):

   • Query: Compute the sum over the range \([1, S_i]\) using the BIT. This gives the answer \(P_i\), which is “what position from the left is \(S_i\) among the available spaces.”
   • Update: Subtract \(1\) from the value at position \(S_i\) to make it \(0\) (mark it as occupied).

Concrete Example (\(N = 5\), \(M = 3\), \(S = [3, 1, 4]\))

Operation	Available Spaces	\(S_i\)	Number of available spaces in \([1, S_i]\)	Answer \(P_i\)
Initial	1,2,3,4,5	-	-	-
1st book	1,2,3,4,5	3	3	3
2nd book	1,2,4,5	1	1	1
3rd book	2,4,5	4	2	2

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Initialization: \(N\) updates, each \(O(\log N)\) → \(O(N \log N)\)
  • Placing each book: \(M\) queries and updates, each \(O(\log N)\) → \(O(M \log N)\)
• Space complexity: \(O(N)\)
  • Array size for the BIT

Implementation Notes

1. 1-indexed BIT: BIT is typically implemented as 1-indexed. Since the storage space numbers also start from 1, this works well together.

2. Direction of updates:

   • update(i, delta): Adds delta to position \(i\). Internally, it propagates to parent nodes via i += i & (-i).
   • query(i): Computes the sum from position \(1\) to \(i\). It traverses child nodes via i -= i & (-i).

3. Changing from available to occupied: To change from an initial value of \(1\) (available) to \(0\) (occupied), call update(s, -1).

   Source Code

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    
    # BITを使って空いているスペースを管理
    # 初期状態では全てのスペースが空いている（各位置に1を設定）
    bit = BinaryIndexedTree(N)
    for i in range(1, N + 1):
        bit.update(i, 1)
    
    results = []
    for s in S:
        # s番目の収納スペースが、空いているスペースの中で左から何番目かを求める
        # これは1からsまでの区間の和（空いているスペースの数）
        pos = bit.query(s)
        results.append(pos)
        # s番目のスペースを使用済みにする
        bit.update(s, -1)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.