概要

一直線上に並ぶ消防署から、各火災地点 \(P_j\) に対して「未出動の中で最も近い消防車（同距離なら性能が高い方、さらに同点なら番号が小さい方）」を選び、選ばれた消防車を以後使えなくする処理を \(Q\) 回行います。

考察

重要な気づき

消防署の座標は \(X_1 < X_2 < \cdots < X_N\) と昇順に並んでいます。このとき、ある地点 \(P\) に最も近い消防署は通常「\(P\) の直左の消防署」か「\(P\) の直右の消防署」のどちらかです。

今回やっかいなのは、出動済みの消防車（消防署）が途中で消えていくことです。しかしそれでも、

• 「\(P\) より左側にある未出動消防署のうち、最も右のもの（＝左側の最近傍）」
• 「\(P\) 以上の位置にある未出動消防署のうち、最も左のもの（＝右側の最近傍）」

の 2つだけを候補にすれば十分です。
なぜなら、左側でこれより遠い消防署は距離が必ず大きく、右側も同様だからです。

よって各クエリでは、 1. \(P\) の挿入位置（\(X\) のどこに入るか）を二分探索で求める 2. その位置の「未出動の右隣」と「未出動の左隣」を高速に取り出す 3. 2候補を比較して、距離 → 性能 → 番号の順に決める 4. 選ばれた消防署を「未出動集合」から削除する

を繰り返せばよいです。

素朴な方法がダメな理由

各火災ごとに未出動の消防署を全探索して最適を探すと、最悪で \(O(NQ)\) になります。
制約は \(N \le 2 \times 10^5\) なので、これは確実に間に合いません。

必要なのは、「未出動消防署の集合」から 前後（predecessor / successor）を \(O(\log N)\) で取れるデータ構造です。

アルゴリズム

使うデータ構造：Fenwick Tree（BIT）

Fenwick Tree（BIT）を長さ \(N\) の配列として持ち、

• 未出動なら \(1\)
• 出動済みなら \(0\)

を入れて管理します。

BIT でできること： - prefix sum（先頭からの合計）を \(O(\log N)\) - 「累積和が \(k\) 以上になる最小の位置」（k-th 1 の位置）を \(O(\log N)\)

これを利用すると、以下が実現できます。

successor（右側最近の未出動）

「位置 \(i\) 以降で最初に 1 が立っている場所」を求めたい。

• \(i-1\) までの 1 の個数を \(before = sum(i-1)\) とする
• 全体の 1 の個数を \(total = sum(N)\) とする
• \(before == total\) なら右側に未出動はない
• そうでなければ、\((before+1)\) 番目の 1 の位置が successor

predecessor（左側最近の未出動）

「位置 \(i\) 以前で最後に 1 が立っている場所」を求めたい。

• \(cnt = sum(i)\) を「\(i\) までにある 1 の個数」とする
• \(cnt == 0\) なら左側に未出動はない
• そうでなければ、\(cnt\) 番目の 1 の位置が predecessor

クエリ処理の流れ

各火災地点 \(P\) について：

1. bisect_left(X, P) で、\(P\) を挿入できる最左位置 pos（0-based）を求める
   これは「\(X_{pos} \ge P\) となる最小の pos」（存在しなければ \(N\)）を意味します。
2. 1-indexed に直して k = pos + 1 とする（消防署番号と揃える）
3. 右候補 right = successor(k)（\(X \ge P\) 側の最近傍）
4. 左候補 left = predecessor(k-1)（\(X < P\) 側の最近傍）
5. 候補（最大2つ）を次のキーで比較して最小を選ぶ
   
   • 距離：\(|X_i - P|\)
   • 性能：大きいほど優先 → 比較では \(-S_i\)
   • 番号：小さいほど優先 → \(i\)

つまり比較キーは (距離, -性能, 番号)。 6. 選ばれた消防署 best を出力し、BIT に add(best, -1) して未出動から削除する

計算量

• 時間計算量:
  初期化 \(O(N)\)（BIT を全て 1 で構築）
  各クエリで二分探索 \(O(\log N)\) ＋ predecessor/successor \(O(\log N)\) ＋ 削除 \(O(\log N)\)
  よって合計 \(O((N+Q)\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 「最近傍候補は左右の2つだけ」という性質が核です。全体から最小距離を探さないようにします。

• BIT は 1-indexed なので、bisect_left の結果（0-indexed）を k = pos + 1 に直しています。

• 同距離のときの優先順位（性能が大きい、さらに番号が小さい）を忘れないよう、比較キーを (distance, -S[i], i) にしています。

• 出動済みの削除は BIT に -1 を加えるだけでよく、集合を直接操作する必要がありません。

  ソースコード

import sys
from bisect import bisect_left

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

    def add(self, i: int, v: int) -> None:
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += v
            i += i & -i

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

    def kth(self, k: int) -> int:
        # 1-indexed: smallest idx with prefix sum >= k (k in [1..total])
        idx = 0
        bit = self.bit
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= self.n and bit[nxt] < k:
                idx = nxt
                k -= bit[nxt]
            step >>= 1
        return idx + 1

    def successor(self, i: int):
        if i < 1:
            i = 1
        if i > self.n:
            return None
        total = self.sum(self.n)
        before = self.sum(i - 1)
        if before == total:
            return None
        return self.kth(before + 1)

    def predecessor(self, i: int):
        if i < 1:
            return None
        if i > self.n:
            i = self.n
        cnt = self.sum(i)
        if cnt == 0:
            return None
        return self.kth(cnt)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    X = [0] * (N + 1)
    S = [0] * (N + 1)
    X0 = [0] * N  # 0-based for bisect

    for i in range(1, N + 1):
        xi = next(it)
        si = next(it)
        X[i] = xi
        S[i] = si
        X0[i - 1] = xi

    fw = Fenwick(N)

    out_lines = []
    for _ in range(Q):
        p = next(it)
        pos = bisect_left(X0, p)  # 0..N
        k = pos + 1               # 1..N+1

        right = fw.successor(k)
        left = fw.predecessor(k - 1)

        best = None
        best_key = None

        if left is not None:
            best = left
            best_key = (p - X[left] if p >= X[left] else X[left] - p, -S[left], left)
        if right is not None:
            key = (X[right] - p if X[right] >= p else p - X[right], -S[right], right)
            if best is None or key < best_key:
                best = right
                best_key = key

        out_lines.append(str(best))
        fw.add(best, -1)

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

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。