概要

\(N\) 個の区画から \(M\) 回の範囲指定で果物を収穫する問題です。一度収穫した区画からは二度と収穫できないため、与えられた複数の範囲の「和集合」に含まれる区画の果物量の合計を効率よく求める必要があります。

考察

1. 素朴なアプローチとその限界

各収穫作業 \([L_j, R_j]\) に対して、その範囲内の区画を一つずつ確認し、「まだ収穫されていないなら合計に加算し、収穫済みにする」という処理を繰り返すと、最悪の場合で \(O(N \times M)\) の時間がかかってしまいます。本問題では \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

2. 区間の重なりを解消する

「一度収穫するとなくなる」という条件は、「与えられた \(M\) 個の区間の和集合（重複を取り除いた範囲）に含まれる区画の合計値を求める」と言い換えることができます。 例えば、区間 \([1, 3]\) と \([2, 5]\) が与えられた場合、これらを統合して一つの区間 \([1, 5]\) として扱うことができます。このように、重なり合う区間を統合して「互いに素（重なりがない）」な状態にすれば、各区画を重複して数える心配がなくなります。

3. 範囲和の高速化

統合された後の区間 \([L, R]\) の合計収穫量を求める際、毎回ループで足し合わせると時間がかかります。これは、あらかじめ累積和（Prefix Sum）を計算しておくことで、任意の範囲の合計を \(O(1)\) で求めることができます。

アルゴリズム

以下の手順で解を求めます。

1. 累積和の準備: 各区画の果物量 \(A_i\) に対して、累積和 \(S[i] = A_1 + A_2 + \dots + A_i\) を計算しておきます。これにより、範囲 \([L, R]\) の合計は \(S[R] - S[L-1]\) で計算可能になります。
2. 区間のソート: \(M\) 個の収穫範囲 \([L_j, R_j]\) を、左端 \(L_j\) が小さい順にソートします。
3. 区間の統合（Interval Merging）: ソートされた区間を順番に見ていき、現在の区間と次の区間が重なっている（または接している）場合は、右端を更新して一つの大きな区間にまとめます。重なっていない場合は、現在の区間を確定させ、新しい区間として処理を続けます。
4. 合計の計算: 統合された各区間 \([L', R']\) に対して、累積和を用いて収穫量を計算し、その総和を出力します。

計算量

• 時間計算量: \(O(N + M \log M)\)
  • 累積和の計算に \(O(N)\)
  • 区間のソートに \(O(M \log M)\)
  • 区間の統合と合計の計算に \(O(M)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 累積和配列の保持に \(O(N)\)、区間データの保持に \(O(M)\) 必要です。

実装のポイント

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

• 累積和のインデックス: \(S[0] = 0\) とし、サイズ \(N+1\) の配列を用意することで、範囲 \([L, R]\) の計算を \(S[R] - S[L-1]\) と簡潔に記述できます。

• 区間の統合判定: ソート済みであれば、「次の区間の左端 \(\leq\) 現在の区間の右端」であるかを確認するだけで重なりを判定できます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 区画の数, M: 収穫作業の回数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各区画の果物量 A_i の累積和を計算する
    # S[i] には A_1 + A_2 + ... + A_i が格納される
    S = [0] * (N + 1)
    # A_1, A_2, ..., A_N は input_data[2] から input_data[N+1] に格納されている
    A_vals = map(int, input_data[2:N+2])
    for i, val in enumerate(A_vals):
        S[i+1] = S[i] + val
        
    # 各収穫作業の範囲 [L_j, R_j] を取得する
    # L_j, R_j のペアは input_data[N+2] 以降に格納されている
    coords = map(int, input_data[N+2:])
    intervals = []
    for l in coords:
        try:
            r = next(coords)
            intervals.append((l, r))
        except StopIteration:
            break
    
    # 収穫範囲を左端（L_j）の昇順でソートする
    intervals.sort()
    
    if not intervals:
        sys.stdout.write('0\n')
        return
        
    # 重なり合う、または接している収穫範囲を統合する
    # これにより、実際に収穫される区画の集合を互いに素な区間の集合として表す
    merged = []
    curr_l, curr_r = intervals[0]
    for i in range(1, len(intervals)):
        next_l, next_r = intervals[i]
        # 次の区間の左端が現在の区間の右端以下であれば、重なりまたは接している
        if next_l <= curr_r:
            # 右端をより遠い方に更新する
            if next_r > curr_r:
                curr_r = next_r
        else:
            # 重なりがない場合、現在の区間を確定させて新しい区間を開始する
            merged.append((curr_l, curr_r))
            curr_l, curr_r = next_l, next_r
    # 最後の区間を追加する
    merged.append((curr_l, curr_r))
    
    # 統合された各区間について、累積和を用いて収穫量の合計を計算する
    total_harvest = 0
    for l, r in merged:
        # 区間 [l, r] の合計は S[r] - S[l-1] で求められる
        total_harvest += S[r] - S[l-1]
    
    # 結果を出力する
    sys.stdout.write(str(total_harvest) + '\n')

if __name__ == '__main__':
    solve()

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