Overview

Given \(N\) fields divided into \(M\) contiguous sections, we need to calculate the total harvest (productivity) of each section and find the difference between the “maximum” and “minimum” values.

Analysis

The core of this problem is “how to efficiently compute the sum over a specified range.”

1. Naive Approach and Its Limitations

What happens if we loop from \(L_j\) to \(R_j\) each time to compute the sum for each section? In the worst case, the length of a single section can be close to \(N\), so one computation takes \(O(N)\). Since there are \(M\) sections, the overall time complexity becomes \(O(N \times M)\). Given the constraints of this problem where \(N, M \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which will not fit within the time limit (typically around 2 seconds).

2. Optimization Using Prefix Sums

Prefix Sum is an effective technique for quickly computing sums over contiguous ranges. We precompute the cumulative sum from the first field to each position: - \(P_0 = 0\) - \(P_1 = A_1\) - \(P_2 = A_1 + A_2\) - \(P_i = A_1 + A_2 + \dots + A_i\)

With this preparation, the sum from field \(L\) to field \(R\) can be computed in \(O(1)\) using the following formula: $\(\text{Sum} = P_R - P_{L-1}\)$ This makes it possible to process a large number of sections efficiently.

Algorithm

1. Build the prefix sum array: Read the harvest values \(A_i\) in order and construct the prefix sum array \(P\).
2. Compute each section: For the given \(M\) ranges \((L_j, R_j)\), use the prefix sum to calculate the productivity of each section.
3. Update maximum and minimum: Sequentially compare the computed productivities and record the overall maximum max_prod and minimum min_prod.
4. Output the result: Compute and output max_prod - min_prod.

Complexity

• Time complexity: \(O(N + M)\)
  • Building the prefix sum takes \(O(N)\), and computing each section (\(M\) times) takes \(O(M)\). Including input reading, everything can be processed in linear time.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the harvest data and the prefix sum array.

Implementation Notes

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

• Index adjustment: Since field numbers start from \(1\) (1-indexed), set the size of the prefix sum array \(P\) to \(N+1\) and place \(0\) at the beginning. This allows the range calculation \(P_R - P_{L-1}\) to be implemented without off-by-one errors.

• Initial value setting: For initializing the minimum value, use a sufficiently large value (such as float('inf')).

  Source Code

import sys
from itertools import accumulate

def solve():
    # 標準入力からすべてのデータを一括で読み込み、空白で分割します。
    # これは大規模な入力（N, M = 2 * 10^5）を高速に処理するための一般的な手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを整数のリストに変換します。
    data = list(map(int, input_data))
    
    # 最初の2つの値は N（畑の数）と M（区画の数）です。
    N = data[0]
    M = data[1]
    
    # 畑の収穫量 A_1 から A_N は、data[2] から data[N+1] に格納されています。
    # 累積和（Prefix Sum）を計算して、任意の区間の合計を O(1) で求められるようにします。
    # P[i] は 畑 1 から 畑 i までの収穫量の合計を保持します。
    # P[0] = 0, P[1] = A_1, P[2] = A_1 + A_2, ..., P[N] = sum(A_1...A_N)
    P = [0] + list(accumulate(data[2:N+2]))
    
    # 各区画の生産力の最大値と最小値を追跡するための変数を初期化します。
    # 収穫量 A_i は 1 以上なので、生産力の最小値は非常に大きな値で、最大値は -1 で初期化します。
    max_prod = -1
    min_prod = float('inf')
    
    # 各区画の範囲 (L_j, R_j) は、data[N+2] 以降に順番に格納されています。
    # イテレータを使用して、L と R をペアで取り出します。
    it = iter(data[N+2:])
    for _ in range(M):
        # L と R は 1-indexed の畑番号です。
        try:
            L = next(it)
            R = next(it)
        except StopIteration:
            break
        
        # 畑 L から 畑 R までの生産力（収穫量の合計）は、累積和を使って
        # P[R] - P[L-1] で計算できます。
        current_sum = P[R] - P[L-1]
        
        # 最大値と最小値を更新します。
        if current_sum > max_prod:
            max_prod = current_sum
        if current_sum < min_prod:
            min_prod = current_sum
            
    # 最も生産力の高い区画と最も低い区画の差を出力します。
    if max_prod == -1:
        # M=0 の場合は問題の制約上発生しませんが、念のため 0 を出力します。
        print(0)
    else:
        print(max_prod - min_prod)

if __name__ == '__main__':
    solve()

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