概要

複数回の範囲回収（区間）で集められるコインの総和を求めます。重複して回収できないため、実質的には「全ての魔法区間の和集合に含まれる宝箱のコイン合計」を計算します。

考察

重要な気づき

• ある宝箱は、魔法の範囲に一度でも入ればコインを回収され、それ以降は回収されません。
• つまり各宝箱は「少なくとも1つの区間 \([L_j, R_j]\) に含まれるかどうか」だけが重要です。
• よって問題は、\(M\) 個の区間の和集合に含まれる宝箱（点）を集め、そのコインを合計する問題に言い換えられます。

素朴な方法がダメな理由

• 各魔法ごとに「その区間内の宝箱を全部探して加算」すると、最悪で \(M \times N = 4 \times 10^{10}\) となり確実にTLEです。
• また、区間が重なっていると同じ宝箱を何度も数えてしまい、重複除去も必要になります。

解決方針

1. まず区間をソートして重なりをマージ（併合）し、互いに交わらない区間列（和集合）を作る。
2. 宝箱も座標でソートしておき、マージ済み区間を左から順に見ながら、二本のポインタで該当する宝箱だけを一度ずつ加算する。

（例） - 区間が \([1,5], [3,7], [10,12]\) なら、和集合は \([1,7], [10,12]\)。 - 宝箱はこの2区間に入るものだけ数えればよく、重複カウントも起きません。

アルゴリズム

1. 宝箱 \((X_i, C_i)\) を座標 \(X_i\) で昇順ソートする。
2. 区間 \((L_j, R_j)\) を \(L_j\) で昇順ソートする。
3. ソート済み区間を左から走査し、重なる（または隣接する）区間をマージして merged を作る。
   
   • 現在の区間を \((cur\_l, cur\_r)\) として保持
   • 次の区間 \((l, r)\) が \(l \le cur\_r + 1\) なら連結できるので \(cur\_r = \max(cur\_r, r)\)
   • そうでなければ確定して merged に追加し、新しい区間を開始
4. merged の各区間 \([l, r]\) について、宝箱配列をポインタ i で進める：
   • \(X_i < l\) の宝箱はこの区間に入らないので捨てて進める
   • \(l \le X_i \le r\) の間はコインを加算しつつ進める
   • 宝箱は昇順なので、一度進めた i は戻らず、全宝箱を高々1回ずつ処理できる

この方法により「区間の重複による二重回収」を、区間マージによって自然に解消できます。

計算量

• 時間計算量: \(O(N \log N + M \log M)\)（宝箱と区間のソートが支配的。走査自体は \(O(N+M)\)）
• 空間計算量: \(O(N + M)\)（入力保持とマージ結果）

実装のポイント

• 区間マージでは、重なりだけでなく「隣接」もまとめています（条件 \(l \le cur\_r + 1\)）。今回は宝箱が整数座標なので、隣接をマージしても答えは変わらず、実装が簡潔になります。

• merged を左から処理する際、宝箱側のポインタ i を使って一方向に進めると、重複なく高速に集計できます。

• コイン枚数や合計は最大で \(N \times 10^9\) 程度になりうるため、Pythonでは問題ありませんが、他言語では \(64\) bit 整数（long long）が必要です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    chests = []
    for _ in range(N):
        x = next(it)
        c = next(it)
        chests.append((x, c))

    intervals = []
    for _ in range(M):
        l = next(it)
        r = next(it)
        intervals.append((l, r))

    chests.sort()
    intervals.sort()

    merged = []
    if intervals:
        cur_l, cur_r = intervals[0]
        for l, r in intervals[1:]:
            if l <= cur_r + 1:
                if r > cur_r:
                    cur_r = r
            else:
                merged.append((cur_l, cur_r))
                cur_l, cur_r = l, r
        merged.append((cur_l, cur_r))

    ans = 0
    i = 0
    for l, r in merged:
        while i < N and chests[i][0] < l:
            i += 1
        while i < N and chests[i][0] <= r:
            ans += chests[i][1]
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。