Overview

This is a problem where you harvest fruits from \(N\) plots across \(M\) range-specified operations. Since a plot that has already been harvested cannot be harvested again, you need to efficiently compute the total fruit amount in the plots contained in the union of the given multiple ranges.

Analysis

1. Naive Approach and Its Limitations

For each harvest operation \([L_j, R_j]\), if you check each plot within the range one by one—”if not yet harvested, add to the total and mark as harvested”—this takes \(O(N \times M)\) time in the worst case. Since \(N, M \leq 2 \times 10^5\) in this problem, this requires up to approximately \(4 \times 10^{10}\) computations, which will not fit within the time limit.

2. Resolving Interval Overlaps

The condition “once harvested, it’s gone” can be rephrased as “find the total value of plots contained in the union (with overlaps removed) of the given \(M\) intervals.” For example, if intervals \([1, 3]\) and \([2, 5]\) are given, they can be merged into a single interval \([1, 5]\). By merging overlapping intervals into a “disjoint (non-overlapping)” state, we no longer need to worry about counting any plot more than once.

3. Fast Range Sum Computation

When computing the total harvest for a merged interval \([L, R]\), summing with a loop each time is slow. By precomputing a prefix sum, we can obtain the sum of any range in \(O(1)\).

Algorithm

The solution is computed through the following steps:

1. Preparing the Prefix Sum: For the fruit amounts \(A_i\) of each plot, precompute the prefix sum \(S[i] = A_1 + A_2 + \dots + A_i\). This allows the sum of range \([L, R]\) to be computed as \(S[R] - S[L-1]\).
2. Sorting the Intervals: Sort the \(M\) harvest ranges \([L_j, R_j]\) in ascending order of their left endpoints \(L_j\).
3. Interval Merging: Process the sorted intervals in order. If the current interval and the next interval overlap (or are adjacent), update the right endpoint to merge them into one larger interval. If they don’t overlap, finalize the current interval and continue processing with a new interval.
4. Computing the Total: For each merged interval \([L', R']\), compute the harvest amount using the prefix sum, and output the grand total.

Complexity

• Time Complexity: \(O(N + M \log M)\)
  • \(O(N)\) for computing the prefix sum
  • \(O(M \log M)\) for sorting the intervals
  • \(O(M)\) for merging the intervals and computing the total
• Space Complexity: \(O(N + M)\)
  • \(O(N)\) for storing the prefix sum array, and \(O(M)\) for storing the interval data.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Prefix Sum Indexing: By setting \(S[0] = 0\) and preparing an array of size \(N+1\), the range \([L, R]\) sum can be concisely written as \(S[R] - S[L-1]\).

• Interval Overlap Check: When the intervals are sorted, overlap can be determined simply by checking whether “the left endpoint of the next interval \(\leq\) the right endpoint of the current interval.”

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.