概要

この問題は、与えられた \(N\) 個のデータ（山の標高と美しさ）に対して、「標高が一定値以上のものの合計値」を求めるクエリに \(Q\) 回答える問題です。

考察

素朴な方法とその限界

各クエリに対して、すべての山を一つずつチェックして標高が \(L_j\) 以上か判定し、合計を計算する方法（線形探索）が考えられます。 しかし、この方法では 1 回のクエリに \(O(N)\) の時間がかかり、全体で \(O(N \times Q)\) の計算量となります。 本問題の制約では \(N, Q \le 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

高速化のポイント

「特定の範囲の合計を素早く求める」ために、以下の 2 つの工夫を組み合わせます。

1. ソートと二分探索: 山を標高の低い順に並べ替えておけば、「標高が \(L_j\) 以上の山がどこから始まるか」を二分探索によって \(O(\log N)\) で見つけることができます。
2. 累積和（後ろから）: ある地点から最後までの合計値をあらかじめ計算しておく累積和（逆方向）を用いることで、範囲内の合計値を \(O(1)\) で取得できます。

これにより、各クエリに対して \(O(\log N)\) で回答できるようになります。

アルゴリズム

1. データの整理: 山の標高 \(Y_i\) と美しさ \(P_i\) をペアとしてまとめ、標高 \(Y\) の昇順にソートします。
2. 累積和の計算: ソートした後の美しさの配列に対して、後ろから順に合計を計算した配列 suffix_sums を作成します。
   • suffix_sums[i] = (ソート後の \(i\) 番目から最後までの美しさの合計)
   • suffix_sums[N] = 0 としておくと便利です。
3. クエリへの回答: 各基準標高 \(L_j\) に対して以下を行います。
   • 二分探索（Pythonでは bisect_left）を用いて、ソート済みの標高リストの中で \(L_j\) 以上となる最小のインデックス idx を見つけます。
   • suffix_sums[idx] が求める答えとなります。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 山のソートに \(O(N \log N)\)
  • 累積和の構築に \(O(N)\)
  • \(Q\) 回の二分探索に \(O(Q \log N)\) かかります。
• 空間計算量: \(O(N + Q)\)
  • 山のデータ、累積和配列、およびクエリの回答を保持するために必要です。

実装のポイント

• 高速な入出力: \(N\) と \(Q\) が大きいため、Pythonでは sys.stdin.read().split() や sys.stdout.write を使用して入出力のボトルネックを解消しています。

• 二分探索: 標高がちょうど \(L_j\) の山が含まれる場合も考慮し、bisect_left を使用して「\(L_j\) 以上」の境界を正しく取得します。

• 累積和のインデックス: suffix_sums のサイズを \(N+1\) にすることで、すべての山が条件を満たさない（idx = N となる）場合でもエラーにならず 0 を返せるようにしています。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    # 入力を一度にすべて読み込む（高速化のため）
    data = sys.stdin.read().split()
    if not data:
        return
    
    # すべての文字列を整数に変換
    nums = list(map(int, data))
    
    N = nums[0]
    Q = nums[1]
    
    # 山の標高(Y)と評価値(P)をスライスで抽出
    # Yはインデックス 2, 4, ..., 2 + 2*N - 2
    # Pはインデックス 3, 5, ..., 2 + 2*N - 1
    Y = nums[2:2+2*N:2]
    P = nums[3:2+2*N:2]
    
    # 標高 Y に基づいて山をソートする
    # zipを使用して (標高, 評価値) のペアを作成しソート
    mountains = sorted(zip(Y, P))
    
    # ソートされた結果から標高と評価値をそれぞれ分離
    if N > 0:
        heights, beauties = zip(*mountains)
    else:
        heights, beauties = (), ()
    
    # 評価値の累積和（後ろから）を計算
    # suffix_sums[i] は、ソート後の i 番目以降のすべての山の評価値の合計
    suffix_sums = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        suffix_sums[i] = suffix_sums[i+1] + beauties[i]
    
    # 調査（クエリ）の基準標高 L は、山のデータ以降に格納されている
    queries = nums[2+2*N:]
    results = []
    
    # 各調査に対して二分探索を用いて答えを求める
    for l in queries:
        # bisect_left で標高が l 以上となる最初のインデックスを取得
        idx = bisect_left(heights, l)
        # そのインデックス以降の評価値の合計を累積和配列から取得
        results.append(str(suffix_sums[idx]))
    
    # すべての答えを改行区切りで一括出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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