Overview

Given a partitioning of fields into sections, find the difference between the maximum and minimum productivity (sum of harvests) among all sections.

Analysis

Each section consists of consecutive fields, and the productivity of each section is the sum of the harvest amounts of the fields within that interval.
A naive approach that loops from \(L_j\) to \(R_j\) for each section to compute the sum would require \(O(N \times M)\) computation in the worst case. Given the constraints \(N, M \sim 2 \times 10^5\), this may not finish within the time limit (TLE).

To solve this, we use “prefix sums.”
By precomputing a prefix sum array \(S[i] = A_1 + A_2 + \cdots + A_{i-1}\), the sum of any interval \([L, R]\) can be obtained in \(O(1)\) as \(S[R] - S[L-1]\).
This reduces the overall time complexity to \(O(N + M)\).

Algorithm

1. Read input efficiently (using sys.stdin.read).
2. Build the prefix sum array \(S\) from the harvest amounts:
   • \(S[0] = 0\)
   • \(S[i] = S[i-1] + A[i-1]\)
3. For each section, compute the interval sum from \(L_j\) to \(R_j\) using the prefix sum:
   • Section productivity = \(S[R_j] - S[L_j - 1]\)
4. Track and update the maximum and minimum productivity values.
5. Output the difference between the maximum and minimum values.

Example

For example, if \(A = [10, 20, 30, 40]\) and the sections are \([1,2]\) and \([3,4]\): - Prefix sums: \(S = [0, 10, 30, 60, 100]\) - Section 1 productivity: \(S[2] - S[0] = 30 - 0 = 30\) - Section 2 productivity: \(S[4] - S[2] = 100 - 30 = 70\) - Difference: \(70 - 30 = 40\)

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Use sys.stdin.read for fast input reading (important in Python)
• Be careful with prefix sum indexing (\(S[0] = 0\), \(A[i]\) corresponds to \(S[i+1]\))
• Be careful with initial values for max/min (initialize max with a sufficiently small value, min with a sufficiently large value)

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    max_prod = -1
    min_prod = float('inf')
    
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        prod = S[R] - S[L-1]
        if prod > max_prod:
            max_prod = prod
        if prod < min_prod:
            min_prod = prod
    
    print(max_prod - min_prod)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.