Overview

This is a problem where you need to compute the total harvest for each section (contiguous interval), then output the difference between the maximum and minimum section totals.

Analysis

The productivity of section \([L_j, R_j]\) is \(A_{L_j}+A_{L_j+1}+\cdots+A_{R_j}\).
If we naively sum this for each section, in the worst case (e.g., \(M=N\) with each section being long), the total computation can reach around \(O(NM)\), which is too slow for \(N \le 2\times 10^5\).

The key insight here is that “range sums” can be computed efficiently using prefix sums.

If we prepare prefix sums \(pref[i] = A_1 + A_2 + \cdots + A_i\), then the range sum is:

• \(sum(L,R) = pref[R] - pref[L-1]\)

which can be computed in \(O(1)\).

For example, when \(A = [3,1,4,1,5]\),
\(pref = [0,3,4,8,9,14]\) (placing \(pref[0]=0\) at the beginning), so the sum of interval \([2,4]\) is \(pref[4]-pref[1]=9-3=6\), computed instantly.

Using this method, we compute each section’s sum sequentially while updating the minimum \(mn\) and maximum \(mx\). Finally, \(mx-mn\) is the answer.

Algorithm

1. Build the prefix sum array \(pref\) from array \(A\).
   
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+A_i\)
2. For each section input \((L, R)\), compute the range sum \(seg = pref[R] - pref[L-1]\).
3. Update the minimum \(mn\) and maximum \(mx\) of \(seg\).
4. Output \(mx - mn\) at the end.

Complexity

• Time complexity: \(O(N + M)\) (prefix sum construction is \(O(N)\), processing each section is \(O(M)\))
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• Since we use \(pref[L-1]\), preparing \(pref[0]=0\) and using 1-indexed arrays makes implementation easier.

• Harvest values and range sums can be as large as \(10^9 \times 2\times 10^5\), so while Python handles this naturally, other languages require 64-bit integers.

• Since the input can be large, reading it efficiently with sys.stdin.buffer.read() as shown in the code is recommended.

  Source Code

import sys

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

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    pref = [0] * (N + 1)
    s = 0
    for i in range(1, N + 1):
        s += A[i]
        pref[i] = s

    mn = None
    mx = None
    for _ in range(M):
        L = next(it)
        R = next(it)
        seg = pref[R] - pref[L - 1]
        if mn is None or seg < mn:
            mn = seg
        if mx is None or seg > mx:
            mx = seg

    print(mx - mn)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.