概要

\(N\) 箇所の消防署から、発生した火災地点に最も近い「まだ出動していない」消防車を順次選んでいく問題です。距離が同じ場合のタイブレーク（性能値、消防署番号）を考慮しながら、効率的に候補を見つける必要があります。

考察

1. 候補となる消防車の絞り込み

火災が発生した座標 \(P_j\) に対して、出動候補となる消防車は以下の2つに絞られます。 - 座標 \(P_j\) より左側（\(X_i \leq P_j\)）にあり、現在待機中の消防署の中で、最も \(P_j\) に近いもの。 - 座標 \(P_j\) より右側（\(X_i \geq P_j\)）にあり、現在待機中の消防署の中で、最も \(P_j\) に近いもの。

これら2つの候補を比較し、問題文の優先順位（距離 \(\to\) 性能値 \(\to\) 番号）に従って1台を選びます。

2. 素朴な解法の限界

各火災通報に対して、すべての消防署を走査して待機中かつ最短距離のものを探すと、1回あたり \(O(N)\) かかります。全体で \(O(NQ)\) となり、 \(N, Q \leq 2 \times 10^5\) の制約下では実行時間制限に間に合いません。

3. 高速化のポイント

「待機中の消防署の中から、特定のインデックスに近いものを探す」という操作を高速化する必要があります。 消防署は座標順に並んでいるため、二分探索を利用したいところですが、消防車が出動するたびに「待機中」の状態が変化するため、単純な配列では対応できません。

そこで、フェニック木（BIT: Binary Indexed Tree） を利用します。 - 各消防署が待機中なら 1、出動済みなら 0 と管理します。 - bisect で \(P_j\) の挿入位置（インデックス \(k\)）を求めます。 - BIT上での累積和を用いることで、「インデックス \(k\) 未満に待機中の消防車が何台あるか」が分かります。 - BIT上の二分探索（Binary Lifting） を用いることで、「\(m\) 番目に存在する待機中の消防署のインデックス」を \(O(\log N)\) で特定できます。

アルゴリズム

1. 初期化:
   • 消防署の座標 \(X\) と性能値 \(S\) を読み込みます。
   • BITを構築し、全 \(N\) 箇所を 1（待機中）に設定します。
2. 各クエリ \(P_j\) に対して:
   • bisect_left を使い、 \(X_i \geq P_j\) となる最小のインデックス \(k\) を求めます。
   • BITの累積和により、インデックス \(k\) より左側にある待機中の消防車の総数 count_before を計算します。
   • 左側の候補: count_before 番目の待機中の消防署をBIT上の二分探索で探します。
   • 右側の候補: count_before + 1 番目の待機中の消防署をBIT上の二分探索で探します。
   • 2つの候補から、距離・性能値・番号の優先順位に従って1つを選択します。
   • 選択した消防署のBITの値を 0 に更新（-1 加算）し、出動済みにします。
3. 出力:
   • 各クエリで選ばれた消防署の番号を順に出力します。

計算量

• 時間計算量: \(O(N + Q \log N)\)
  • BITの初期構築に \(O(N)\)。
  • 各クエリにおいて、二分探索（bisect）とBIT上の二分探索（Binary Lifting）、BITの更新がいずれも \(O(\log N)\) です。
• 空間計算量: \(O(N)\)
  • 消防署の情報およびBITを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• BIT上の二分探索: 普通の二分探索とBITのクエリを組み合わせると \(O(\log^2 N)\) になりますが、BITの構造を利用した Binary Lifting を行うことで \(O(\log N)\) に落とすことができます。

• 高速な入出力: Pythonではデータ量が多い場合、sys.stdin.read().split() や sys.stdout.write を使うことで実行時間を大幅に短縮できます。

• 1-indexed: BITは通常 1-indexed で実装するため、消防署の 0-indexed な管理との変換に注意が必要です。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    # Fast I/O: Reading all input at once is efficient in Python
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: Number of fire stations, Q: Number of fire calls
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # Coordinates X and performance values S for each station
    # Stations are given in increasing order of X_i
    X = [int(input_data[i]) for i in range(2, 2 + 2 * N, 2)]
    S = [int(input_data[i]) for i in range(3, 2 + 2 * N, 2)]
    # Fire call coordinates P
    P = [int(input_data[i]) for i in range(2 + 2 * N, 2 + 2 * N + Q)]

    # Fenwick Tree (BIT) to track available stations
    # bit[i] stores the count of available stations in a range
    # Initializing BIT in O(N) where each station is initially available (1)
    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] = i & -i
    
    # Number of bits required for binary lifting on BIT
    blen = N.bit_length()
    
    results = []
    total_available = N
    
    for pj in P:
        # Find the index where the fire coordinate pj would be inserted in X
        # k is the smallest index such that X[k] >= pj
        k = bisect_left(X, pj)
        
        # Count available stations with index < k (stations to the left of pj)
        # This is equivalent to bit_query(k)
        count_before = 0
        temp_k = k
        while temp_k > 0:
            count_before += bit[temp_k]
            temp_k -= temp_k & -temp_k
        
        i_L = -1 # Nearest available station to the left
        i_R = -1 # Nearest available station to the right
        
        # Use binary lifting on the BIT to find the k-th available station's index
        # 1. Find the closest available station with index < k (the count_before-th available)
        if count_before > 0:
            idx = 0
            temp_count = count_before
            for i in range(blen - 1, -1, -1):
                next_idx = idx + (1 << i)
                if next_idx <= N:
                    val = bit[next_idx]
                    if val < temp_count:
                        idx = next_idx
                        temp_count -= val
            i_L = idx
            
        # 2. Find the closest available station with index >= k (the (count_before + 1)-th available)
        if count_before < total_available:
            idx = 0
            temp_count = count_before + 1
            for i in range(blen - 1, -1, -1):
                next_idx = idx + (1 << i)
                if next_idx <= N:
                    val = bit[next_idx]
                    if val < temp_count:
                        idx = next_idx
                        temp_count -= val
            i_R = idx
            
        # Tie-breaking logic:
        # Distance (min) > Performance (max) > Station Index (min)
        if i_L != -1 and i_R != -1:
            dL = pj - X[i_L]
            dR = X[i_R] - pj
            if dL < dR:
                chosen = i_L
            elif dR < dL:
                chosen = i_R
            else:
                # Distances are equal, compare performance values
                if S[i_L] > S[i_R]:
                    chosen = i_L
                elif S[i_R] > S[i_L]:
                    chosen = i_R
                else:
                    # Performances are equal, pick smaller index
                    chosen = i_L # i_L is always < i_R
        elif i_L != -1:
            chosen = i_L
        else:
            chosen = i_R
            
        # Store the 1-indexed station number
        results.append(chosen + 1)
        
        # Update BIT: Mark the chosen station as unavailable (set to 0)
        temp_idx = chosen + 1
        while temp_idx <= N:
            bit[temp_idx] -= 1
            temp_idx += temp_idx & -temp_idx
        total_available -= 1
        
    # Final output using fast join and sys.stdout
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。