Overview

This problem asks us to find the difference between the maximum and minimum values of the total harvest (productivity) for each section, when dividing \(N\) fields into \(M\) consecutive sections.

Analysis

Key Insight for Solving the Problem

The productivity of each section is “the sum of harvests from consecutive fields.” For example, the productivity of a section from field \(L\) to field \(R\) is \(A_L + A_{L+1} + \cdots + A_R\).

Problems with the Naive Approach

Let’s consider a method where we sum up the harvests of fields in the range for each section every time.

For each section: calculate A[L] + A[L+1] + ... + A[R]

With this method, calculating one section takes at most \(O(N)\), and since there are \(M\) sections, the total time complexity is \(O(NM)\). When \(N, M\) are at most \(2 \times 10^5\), this requires up to about \(4 \times 10^{10}\) calculations in the worst case, resulting in TLE (Time Limit Exceeded).

Solution: Using Prefix Sum

Using prefix sum, we can calculate the sum of a consecutive interval in \(O(1)\).

Define the prefix sum array \(S\) as follows: - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\) (for \(i \geq 1\))

Then, the sum from field \(L\) to field \(R\) can be calculated as: $\(A_L + A_{L+1} + \cdots + A_R = S[R] - S[L-1]\)$

Concrete Example

If the field harvests are \(A = [3, 1, 4, 1, 5]\):

\(i\)	0	1	2	3	4	5
\(S[i]\)	0	3	4	8	9	14

• Sum from field 2 to field 4: \(S[4] - S[1] = 9 - 3 = 6\) (indeed \(1 + 4 + 1 = 6\) ✓)

Algorithm

1. Build prefix sum: Create prefix sum array \(S\) from array \(A\)
2. Calculate productivity for each section: For each section \((L_j, R_j)\), calculate productivity \(S[R_j] - S[L_j - 1]\) in \(O(1)\)
3. Update maximum and minimum: Update maximum and minimum values using the calculated productivity
4. Output the difference: Output maximum \(-\) minimum

Complexity

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

  • Building prefix sum takes \(O(N)\)
  • Calculating productivity for each section takes \(O(M)\) (\(O(1)\) per section)

• Space complexity: \(O(N)\)

  • Size of prefix sum array

Implementation Notes

1. Converting between 1-indexed and 0-indexed:

   • In the problem statement, field numbers start from \(1\) (1-indexed)
   • Python arrays start from \(0\) (0-indexed)
   • Build the prefix sum array as prefix_sum[i+1] = prefix_sum[i] + A[i], and find the sum of interval \([L, R]\) with prefix_sum[R] - prefix_sum[L-1]

2. Watch out for overflow:

   • \(A_i\) is at most \(10^9\), and there are at most \(2 \times 10^5\) fields, so the sum can be at most about \(2 \times 10^{14}\)
   • In Python, integer overflow is handled automatically, so there’s no problem (in C++ etc., long long is required)

3. Fast input:

   • Using sys.stdin.readline allows fast reading of large amounts of input

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate prefix sum
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + A[i]
    
    min_prod = float('inf')
    max_prod = float('-inf')
    
    for _ in range(M):
        L, R = map(int, input().split())
        # Calculate section productivity (L, R are 1-indexed)
        prod = prefix_sum[R] - prefix_sum[L - 1]
        min_prod = min(min_prod, prod)
        max_prod = max(max_prod, prod)
    
    print(max_prod - min_prod)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.