Overview

Given \(M\) intervals, this problem asks for the sum of fruits in sections that are included in at least one interval. This can be solved efficiently using the imos method (difference array technique).

Analysis

The Essence of the Problem

Even if you harvest from the same section multiple times, the harvest amount is only counted once. In other words, for each section, only “whether it was harvested at least once” matters.

Naive Approach and Its Issues

A straightforward approach would be to check each section from \(L_j\) to \(R_j\) one by one for each harvesting operation.

for each harvesting operation j:
    for i = L_j to R_j:
        mark section i as "harvested"

However, with this method, in the worst case, each harvesting operation processes \(O(N)\) sections, resulting in \(O(N \times M)\) total time complexity. When \(N, M\) are at most \(2 \times 10^5\), this requires \(4 \times 10^{10}\) operations, which will result in TLE (Time Limit Exceeded).

Solution Idea

If we can efficiently calculate “how many times each section was targeted for harvesting,” we just need to add the harvest amount if it’s at least once. To perform this “range addition” quickly, we use the imos method.

Algorithm

What is the Imos Method?

It’s a technique that processes additions to an interval \([L, R]\) in \(O(1)\) using a difference array.

Procedure: 1. Prepare a difference array diff 2. Represent +1 to interval \([L, R]\) as diff[L] += 1 and diff[R+1] -= 1 3. Finally, take the prefix sum to obtain the value at each position

Concrete Example

For \(N = 5\), adding +1 to intervals \([2, 4]\) and \([3, 5]\):

Initial:   diff = [0, 0, 0, 0, 0, 0, 0]  (indices 0 to 6)

[2,4]: diff[2]+=1, diff[5]-=1 → [0, 0, 1, 0, 0, -1, 0]
[3,5]: diff[3]+=1, diff[6]-=1 → [0, 0, 1, 1, 0, -1, -1]

Taking prefix sum:
Position 1: 0
Position 2: 0+1 = 1
Position 3: 1+1 = 2
Position 4: 2+0 = 2
Position 5: 2-1 = 1

Result: Sections 2, 3, 4, 5 are harvested at least once (value > 0)

Application to This Problem

1. For all harvesting operations \((L_j, R_j)\), record them in the difference array
2. While taking the prefix sum, if the count for each section is greater than 0, add \(A_i\) to the total harvest

Complexity

• Time Complexity: \(O(N + M)\)
  • \(M\) interval registrations: \(O(1)\) each, \(O(M)\) total
  • Prefix sum calculation and aggregation for \(N\) sections: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Size of the difference array

Implementation Notes

• Setting the difference array size to \(N + 2\) ensures diff[R + 1] doesn’t go out of bounds
• Section numbers are 1-indexed, while array \(A\) is 0-indexed, so be careful to access with A[i - 1]
• The total harvest can be at most \(N \times \max(A_i) = 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), so it must be handled with 64-bit integers (automatic in Python)

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # To handle range sum queries, manage which sections were harvested
    # Use imos method to determine if each section is harvested at least once
    
    # Use difference array
    diff = [0] * (N + 2)
    
    for _ in range(M):
        L, R = map(int, input().split())
        diff[L] += 1
        diff[R + 1] -= 1
    
    # Take prefix sum to determine if each section was harvested
    total = 0
    count = 0
    for i in range(1, N + 1):
        count += diff[i]
        if count > 0:
            total += A[i - 1]
    
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.