概要

\(N\) 座の山のうち、指定された基準標高 \(L_j\) 以上の山の美しさの合計を、\(Q\) 回のクエリそれぞれについて高速に求める問題です。

考察

素朴なアプローチとその問題点

最も単純な方法は、各クエリごとに全ての山を走査して、標高が \(L_j\) 以上の山の \(P_i\) を合計することです。この場合、1回のクエリに \(O(N)\) かかるため、全体で \(O(NQ)\) となります。\(N, Q\) がともに最大 \(2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の演算が必要になり、TLE（時間制限超過） になります。

重要な気づき

各クエリは「標高 \(L_j\) 以上の山の美しさの合計」を求めるもので、これはある閾値以上の要素の合計という形をしています。もし山を標高順にソートしておけば、「\(L_j\) 以上の山がどこから始まるか」を二分探索で高速に求められます。さらに、そこから末尾までの美しさの合計を累積和（接尾辞和）で事前計算しておけば、\(O(1)\) で答えが得られます。

具体例

山が3座あり、標高順にソートすると以下のようになったとします：

接尾辞和 suffix_sum は末尾から計算します： - suffix_sum[3] = 0 - suffix_sum[2] = 0 + 3 = 3 - suffix_sum[1] = 3 + 8 = 11 - suffix_sum[0] = 11 + 5 = 16

クエリ \(L = 300\) の場合、二分探索でインデックス \(1\) が見つかり、答えは suffix_sum[1] = 11（標高300と500の山の美しさの合計）です。

アルゴリズム

1. 山を標高 \(Y_i\) の昇順にソートする。
2. 接尾辞和（suffix sum）を構築する。suffix_sum[i] は、ソート後のインデックス \(i\) 以降の全ての山の美しさ \(P\) の合計とする。suffix_sum[N] = 0 を初期値とし、\(i = N-1\) から \(0\) まで逆順に suffix_sum[i] = suffix_sum[i+1] + P_i と計算する。
3. 各クエリに対して二分探索を行う。ソート済みの標高配列に対して bisect_left を用いて、標高が \(L_j\) 以上となる最初のインデックス pos を求める。
4. 答えは suffix_sum[pos] となる。該当する山がない場合（pos = N）は suffix_sum[N] = 0 が返される。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • ソートに \(O(N \log N)\)、接尾辞和の構築に \(O(N)\)、各クエリの二分探索に \(O(\log N)\) で \(Q\) 回なので \(O(Q \log N)\)。
• 空間計算量: \(O(N)\)
  • ソート済み配列と接尾辞和配列の分。

実装のポイント

• bisect_left を使うことで、\(L_j\) 以上の最初の位置を正確に求められます。bisect_right ではなく bisect_left を使う理由は、\(L_j\) とちょうど等しい標高の山も含めるためです。

• 接尾辞和を使うことで、「ある位置から末尾まで」の合計を \(O(1)\) で取得できます。先頭からの累積和（prefix sum）でも実現できますが、接尾辞和の方が直感的に分かりやすいです。

• \(P_i\) の値が最大 \(10^9\)、山の数が最大 \(2 \times 10^5\) なので、合計値は最大 \(2 \times 10^{14}\) 程度になります。Python では整数のオーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

• 高速な入出力のために sys.stdin.buffer.read() で一括読み込みし、結果も '\n'.join() でまとめて出力しています。

  ソースコード

import sys
import bisect

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    mountains = []
    for i in range(N):
        Y = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        mountains.append((Y, P))
    
    # Sort by elevation
    mountains.sort(key=lambda x: x[0])
    
    sorted_Y = [m[0] for m in mountains]
    
    # Build suffix sum array
    suffix_sum = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + mountains[i][1]
    
    out = []
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        # Find the first index where Y >= L
        pos = bisect.bisect_left(sorted_Y, L)
        out.append(str(suffix_sum[pos]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

この解説は claude4.6opus-thinking によって生成されました。