概要

各調査で指定された標高以上の山の美しさ評価値の合計を求める問題です。

考察

素朴なアプローチとして、各調査ごとに全ての山を走査して標高をチェックし、条件を満たす山の評価値を足し合わせる方法が考えられます。しかし、\(N\) と \(Q\) が最大で \(2 \times 10^5\) ずつあるため、この方法では計算量が \(O(NQ)\) となり、最大 \(4 \times 10^{10}\) 回の操作が必要になってしまいます。これでは制限時間内に処理できません。

この問題を効率的に解決するには、事前に山のデータを適切に処理しておく必要があります。具体的には、山を標高でソートし、累積和を事前に計算しておくことで、各クエリを高速に処理できるようになります。

アルゴリズム

1. 前処理: すべての山を標高の昇順にソートします
2. 累積和の計算: ソートされた山の評価値の累積和を計算します
3. クエリ処理: 各クエリに対して以下を行います
   • 二分探索で指定された標高 \(L_j\) 以上の最初の山の位置を探す
   • その位置から最後までの山の評価値の合計を累積和を使って求める

例えば、山が標高順にソートされていて、\(i\) 番目以降の山の評価値の合計を求めたい場合、累積和配列 \(\text{prefix\_sum}\) を使って \(\text{prefix\_sum}[n] - \text{prefix\_sum}[i]\) で計算できます。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • ソートに \(O(N \log N)\)
  • 各クエリの二分探索に \(O(\log N)\) で、\(Q\) 回行うので \(O(Q \log N)\)
• 空間計算量: \(O(N)\)
  • 山のデータと累積和を保持するための配列

実装のポイント

• bisect.bisect_left() を使って、指定された標高以上の最初の山の位置を効率的に探します

• 累積和配列は 1-indexed で作成すると、範囲の合計計算が直感的になります（\(\text{prefix\_sum}[r] - \text{prefix\_sum}[l]\) で \(l\) から \(r-1\) までの合計）

• 入力データが多いため、sys.stdin.read() で一括読み込みすると高速です

  ソースコード

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    q = int(data[1])
    index = 2
    
    mountains = []
    for i in range(n):
        y = int(data[index])
        p = int(data[index+1])
        index += 2
        mountains.append((y, p))
        
    mountains.sort(key=lambda x: x[0])
    
    ys = [m[0] for m in mountains]
    ps = [m[1] for m in mountains]
    
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + ps[i]
    
    for i in range(q):
        l = int(data[index])
        index += 1
        
        pos = bisect.bisect_left(ys, l)
        total = prefix_sum[n] - prefix_sum[pos]
        print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。