概要

数直線上の \(N\) 個の宝箱から、 \(M\) 回の範囲指定（魔法）によってコインを回収します。同じ宝箱からは一度しか回収できないという制約のもとで、最終的に得られるコインの総数を求める問題です。

考察

この問題を解く上で、以下の2つの大きなポイントがあります。

1. 「一度しか回収できない」をどう扱うか 複数の魔法の範囲が重なっている場合、その重なった部分にある宝箱を重複して数えてはいけません。これを解決するには、与えられた \(M\) 個の範囲 \([L_j, R_j]\) の和集合（Union）を求めるのが効率的です。重なっている範囲を一つにまとめる（区間スケジューリングの要領でマージする）ことで、互いに重ならない独立した範囲のリストが得られます。

2. 膨大な座標とクエリへの対応 座標が最大 \(10^9\) と非常に大きいため、座標をそのまま配列の添字として使うことはできません。また、魔法の回数 \(M\) も多いため、各魔法ごとに宝箱を一つずつ調べていくと、最悪の場合 \(O(N \times M)\) の時間がかかり、実行時間制限に間に合いません。 宝箱を座標順に並べ替え、累積和と二分探索を組み合わせることで、特定の範囲内にある宝箱のコイン合計を高速に計算できるようにします。

アルゴリズム

1. 宝箱の準備 宝箱を座標 \(X_i\) の昇順にソートします。その後、ソートされた順にコインの枚数 \(C_i\) の累積和 prefix_sum を計算しておきます。これにより、任意のインデックス範囲 \([i, j]\) にある宝箱のコイン合計を \(O(1)\) で計算可能になります。

2. 範囲のマージ \(M\) 個の範囲 \([L_j, R_j]\) を左端 \(L_j\) が小さい順にソートします。端から順に見ていき、前の範囲と重なっている（または接している）場合は範囲を拡張し、重なっていない場合は新しい独立した範囲として保存します。

3. コインの集計 マージされた各範囲 \([L, R]\) について、以下の処理を行います。

   • 二分探索（Pythonでは bisect_left, bisect_right）を用いて、座標 \(L\) 以上の最初の宝箱のインデックスと、座標 \(R\) 以下の最後の宝箱のインデックスを特定します。
   • 特定したインデックス範囲に対応するコインの合計を、手順1で作った累積和を用いて計算し、合計に加算します。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 宝箱のソート: \(O(N \log N)\)
  • 魔法の範囲のソートとマージ: \(O(M \log M)\)
  • 各範囲に対する二分探索: \(O(M \log N)\)
  • 累積和の構築と集計: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • 宝箱の情報、累積和、範囲の情報を保持するために必要です。

実装のポイント

• 高速な入力: \(N, M\) が大きいため、Pythonでは sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• 二分探索の活用: 座標 \(X\) がソート済みであれば、標準ライブラリの bisect モジュールを使うことで、特定の範囲に含まれる要素のインデックスを高速に見つけることができます。

• 区間のマージ: ranges.sort() をした後に、現在の区間の右端と次の区間の左端を比較する処理は、区間問題を解く際の典型的なテクニックです。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    # Read all input at once for fast processing
    # This is efficient for large inputs in Python
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use a pointer to navigate through the input tokens
    ptr = 0
    N = int(input_data[ptr])
    M = int(input_data[ptr+1])
    ptr += 2
    
    # Parse treasure chest information: (position, coins)
    chests = []
    for _ in range(N):
        x = int(input_data[ptr])
        c = int(input_data[ptr+1])
        chests.append((x, c))
        ptr += 2
    
    # Sort chests by their coordinate X to allow binary search and prefix sums
    chests.sort()
    
    # Extract sorted coordinates and calculate prefix sums of coins
    # Prefix sums allow us to calculate the sum of coins in a coordinate range in O(1)
    X = [chest[0] for chest in chests]
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + chests[i][1]
        
    # Parse magic ranges [L, R]
    ranges = []
    for _ in range(M):
        l = int(input_data[ptr])
        r = int(input_data[ptr+1])
        ranges.append((l, r))
        ptr += 2
        
    # Sort magic ranges by their left boundary
    ranges.sort()
    
    # Merge overlapping or adjacent magic ranges to avoid counting the same chest multiple times
    # A chest's coins can only be collected once, so we need the union of all ranges.
    merged_ranges = []
    if M > 0:
        curr_l, curr_r = ranges[0]
        for i in range(1, M):
            next_l, next_r = ranges[i]
            if next_l <= curr_r:
                # Overlapping or touching ranges, update the right boundary
                if next_r > curr_r:
                    curr_r = next_r
            else:
                # Disjoint range found, store the current merged range and start a new one
                merged_ranges.append((curr_l, curr_r))
                curr_l, curr_r = next_l, next_r
        # Append the final merged range
        merged_ranges.append((curr_l, curr_r))
        
    # Calculate the total coins collected across all disjoint merged ranges
    total_coins = 0
    for l, r in merged_ranges:
        # Use binary search (bisect) to find the range of indices of chests within [l, r]
        # start_idx: first chest with X >= l
        # end_idx: first chest with X > r
        start_idx = bisect_left(X, l)
        end_idx = bisect_right(X, r)
        
        # Add the sum of coins for chests in this index range [start_idx, end_idx)
        if start_idx < end_idx:
            total_coins += prefix_sum[end_idx] - prefix_sum[start_idx]
            
    # Output the final result
    print(total_coins)

if __name__ == '__main__':
    main()

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