概要

一直線上に並んだ宝箱に対して、複数の区間で魔法を使ってコインを回収する問題です。同じ宝箱から二重に回収することはできないため、各宝箱は「少なくとも1回カバーされたか否か」だけが重要です。

考察

重要な気づき

一度コインを回収した宝箱からは再度回収できないため、複数の魔法の範囲が重なっていても、その宝箱のコインは 1回だけ 加算されます。

つまり、\(M\) 個の区間 \([L_1, R_1], [L_2, R_2], \ldots, [L_M, R_M]\) の 和集合（union） に含まれる宝箱のコインの合計を求めればよいのです。

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

各魔法ごとに宝箱を1つ1つチェックして「回収済みか？」を管理すると、最悪 \(O(NM)\) の計算量になります。\(N, M\) がともに \(2 \times 10^5\) のとき、\(4 \times 10^{10}\) 回の処理が必要となり TLE になります。

解決策

区間の和集合を効率的に求めるために、区間のマージ（merge） を行います。すべてのクエリ区間をソートして重なる部分を統合すれば、重複なく宝箱を数えられます。

例えば、区間 \([2, 5]\) と \([4, 8]\) は重なっているので \([2, 8]\) にマージされます。\([2, 5]\) と \([7, 8]\) は重なっていないので別々のままです。

アルゴリズム

1. 宝箱を座標順にソートし、コインの 累積和（prefix sum） を作る。
2. クエリ区間をソートし、重なる区間を マージ する。
   • 左端でソートし、次の区間の左端が現在の区間の右端以下なら統合（右端を大きい方に更新）。
   • そうでなければ新しい区間として追加。
3. マージ後の各区間 \([l, r]\) に対して、二分探索で \(l \leq X_i \leq r\) を満たす宝箱のインデックス範囲を求め、累積和で区間のコイン合計を \(O(1)\) で取得する。
4. すべての合計を出力する。

具体例

宝箱: 座標 \([1, 3, 5, 7, 9]\)、コイン \([10, 20, 30, 40, 50]\)

クエリ: \([2, 5], [4, 8]\) → マージすると \([2, 8]\)

\([2, 8]\) に含まれる宝箱は座標 \(3, 5, 7\) → コイン \(20 + 30 + 40 = 90\)

計算量

• 時間計算量: \(O(N \log N + M \log M)\)
  • 宝箱のソートに \(O(N \log N)\)、クエリのソートに \(O(M \log M)\)、マージ後の各区間に対する二分探索は全体で \(O(M \log N)\) （マージ後の区間数は最大 \(M\) 個）
• 空間計算量: \(O(N + M)\)
  • 宝箱の座標・コイン・累積和に \(O(N)\)、クエリの格納に \(O(M)\)

実装のポイント

• 区間のマージ: 左端でソートした後、隣接する区間の左端と現在の右端を比較して統合する定番テクニックです。l <= cr（新しい区間の左端が現在の右端以下）なら重なっているのでマージします。

• 二分探索: Python の bisect_left(sorted_X, l) で \(l\) 以上の最初のインデックス、bisect_right(sorted_X, r) で \(r\) より大きい最初のインデックスを取得し、その範囲の累積和の差を取ります。

• 累積和: 区間内のコインの合計を \(O(1)\) で求めるために、事前に累積和配列を構築しておきます。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    X = []
    C = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        X.append(x)
        C.append(c)
    
    queries = []
    for j in range(M):
        l = int(input_data[idx]); idx += 1
        r = int(input_data[idx]); idx += 1
        queries.append((l, r))
    
    # Sort treasures by coordinate
    treasures = sorted(zip(X, C), key=lambda t: t[0])
    sorted_X = [t[0] for t in treasures]
    sorted_C = [t[1] for t in treasures]
    
    # We need to find all treasure boxes covered by at least one query interval
    # and sum their coins.
    # 
    # Approach: Use a "interval union" approach with sorting, or use a segment-tree
    # style approach to mark collected boxes.
    #
    # Efficient approach: Merge all query intervals, then for each merged interval,
    # sum coins of treasures in that range.
    
    # Merge intervals
    if M == 0:
        print(0)
        return
    
    queries.sort()
    merged = []
    cl, cr = queries[0]
    for i in range(1, M):
        l, r = queries[i]
        if l <= cr:
            cr = max(cr, r)
        else:
            merged.append((cl, cr))
            cl, cr = l, r
    merged.append((cl, cr))
    
    total = 0
    # prefix sum of sorted_C
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + sorted_C[i]
    
    for l, r in merged:
        # Find indices in sorted_X where l <= X <= r
        left_idx = bisect_left(sorted_X, l)
        right_idx = bisect_right(sorted_X, r)
        total += prefix[right_idx] - prefix[left_idx]
    
    print(total)

main()

---

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