Overview

Given \(N\) aligned storage spaces where \(M\) books are placed one by one in order, the problem asks us to determine, just before placing each book, what position that storage space is among the empty spaces counting from the left.

Analysis

Naive Approach and Its Limitations

A straightforward idea is to manage the current vacancy status using a list and count from the left each time a book is placed. However, this approach takes up to \(O(N)\) time when placing the \(i\)-th book. Since there are \(M\) books, the overall time complexity becomes \(O(NM)\), which is too slow for the constraints \(N, M \leq 2 \times 10^5\) within the typical time limit (around 2 seconds).

Efficient Management

The question “what position is this among the empty spaces counting from the left?” can be rephrased as follows: - Assign a value of 1 to each storage space if it is empty, and 0 if it is occupied. - The position of storage space \(S_i\) among the empty spaces equals the sum of values from the \(1\)-st to the \(S_i\)-th space (prefix sum). - After placing a book, update the value of that space from 1 to 0.

When we need to perform both “update a value” and “compute the sum over a range (prefix sum)” operations efficiently, a data structure called the Binary Indexed Tree (BIT / Fenwick Tree) is extremely effective.

Algorithm

Using a Binary Indexed Tree (BIT)

With a BIT, each of the following operations can be performed in \(O(\log N)\): 1. Addition: Add a value to a specified element (in this case, add -1 to change 1 to 0). 2. Prefix Sum: Compute the sum of elements from the \(1\)-st to the \(k\)-th.

Procedure

1. Initialization: Set all \(N\) elements to 1 (empty state) and build the BIT based on this.
2. Processing each book: For \(i = 1, 2, \ldots, M\), do the following:
   • Use the BIT to compute the prefix sum from \(1\) to \(S_i\). This is the answer \(P_i\).
   • Since storage space \(S_i\) becomes occupied, add -1 to the \(S_i\)-th element of the BIT to update it.
3. Output: Output the computed \(P_i\) values in order.

Complexity

• Time Complexity: \(O((N + M) \log N)\)
  • The initial construction of the BIT takes \(O(N \log N)\) (or \(O(N)\) with optimization), and each of the \(M\) queries and updates takes \(O(\log N)\), which is sufficiently fast.
• Space Complexity: \(O(N)\)
  • Required to store the BIT array of length \(N\).

Implementation Notes

• BIT Indexing: BIT is typically implemented as 1-indexed. Since the storage space numbers in the problem also range from \(1\) to \(N\), they can be used directly.

• Fast I/O: Since \(N, M\) can be large, in Python you can eliminate I/O bottlenecks by using sys.stdin.read().split() and sys.stdout.write().

• BIT Initialization: Instead of performing add operations one by one, using a technique like bit[i] = i & -i in the code (bulk initialization leveraging properties of prefix sums) allows the construction to be done in \(O(N)\), which is more efficient.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、空白で分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 収納スペースの総数 N と、配置する本の冊数 M を取得します。
    N = int(input_data[0])
    M = int(input_data[1])
    # 各本を配置する収納スペース番号 S_i を取得します。
    S = [int(x) for x in input_data[2:]]
    
    # Binary Indexed Tree (BIT) を用いて、空いている収納スペースを管理します。
    # bit[i] は、i 番目の収納スペースが空いているか (1) または埋まっているか (0) の累積和を保持します。
    # 初期状態ではすべてのスペースが空いているため、各要素を 1 で初期化した BIT を構築します。
    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] = i & -i
        
    results = []
    for s_val in S:
        # 現在の収納スペース s_val が、空いているスペースの中で左から何番目か（1からs_valまでの累積和）を求めます。
        count = 0
        idx = s_val
        while idx > 0:
            count += bit[idx]
            idx &= idx - 1  # BITのクエリ操作：上位のノードへ移動
        results.append(str(count))
        
        # 本を配置したため、収納スペース s_val を「空いていない (0)」状態に更新します。
        # 具体的には、BIT の s_val 番目の値を -1 します。
        idx = s_val
        while idx <= N:
            bit[idx] -= 1
            idx += idx & (-idx)  # BITの更新操作：影響を受けるノードへ移動
            
    # 全ての結果をまとめて出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.