Overview

This problem asks you to efficiently calculate the number of times each tree is harvested and multiply it by the number of fruits to compute the harvest points. We use the imos method (difference array) to efficiently process range addition operations.

Analysis

Essence of the Problem

The harvest points for each tree \(i\) can be calculated as “number of fruits \(A_i\)” × “number of times harvested”. Therefore, finding how many times each tree was harvested gives us the answer.

Problem with the Naive Approach

If we process the harvests naively for \(M\) days, on day \(j\) we would add 1 to the harvest count for each tree from \(L_j\) to \(R_j\) one by one.

for j in range(M):
    for i in range(L[j], R[j]+1):
        count[i] += 1

In this case, in the worst case we might harvest all \(N\) trees each day, resulting in \(O(N \times M)\) 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: Imos Method

To optimize the operation of “adding \(+1\) uniformly to the range \([L, R]\)”, we use the imos method (difference array).

Algorithm

How the Imos Method Works

Prepare a difference array diff, and when you want to add \(+1\) to the range \([L, R]\): - diff[L] += 1 (the \(+1\) starts here) - diff[R+1] -= 1 (the \(+1\) ends here)

Finally, taking the prefix sum gives us the value at each position.

Concrete Example

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

Recording in the difference array:

Operation	diff[1]	diff[2]	diff[3]	diff[4]	diff[5]	diff[6]
Initial	0	0	0	0	0	0
+1 to [2,4]	0	+1	0	0	-1	0
+1 to [3,5]	0	+1	+1	0	-1	-1

Taking the prefix sum:

Position	1	2	3	4	5
Harvest count	0	1	2	2	1

We can see that tree 2 is harvested 1 time, trees 3 and 4 are harvested 2 times, and tree 5 is harvested 1 time.

Final Answer

For each tree \(i\), calculate the harvest points \(P_i = A_i \times \text{count}[i]\).

Complexity

• Time Complexity: \(O(N + M)\)
  • Recording in the difference array: \(O(1)\) per query × \(M\) queries = \(O(M)\)
  • Prefix sum calculation: \(O(N)\)
  • Final result calculation: \(O(N)\)
• Space Complexity: \(O(N)\)
  • \(O(N)\) needed for each of the difference array and harvest count array

Implementation Notes

1. 0-indexed and 1-indexed conversion: In the problem statement, trees are numbered from 1, but arrays start from 0, so we adjust with diff[L-1] += 1 and diff[R] -= 1.

2. Size of the difference array: To prevent out-of-bounds access, we allocate diff with length \(N+1\) (because we access diff[N] when \(R = N\)).

3. Overflow prevention: Since \(A_i\) can be up to \(10^9\) and the harvest count can be up to \(M = 2 \times 10^5\), the answer can be around \(2 \times 10^{14}\) at maximum. In Python, you don’t need to worry about integer overflow, but in other languages, you need to use 64-bit integer types.

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate how many times each tree is harvested using imos method
    # diff[i]: the amount by which harvest count increases starting from tree i
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R = map(int, input().split())
        diff[L - 1] += 1  # Convert to 0-indexed
        diff[R] -= 1
    
    # Take prefix sum to get the harvest count for each tree
    count = [0] * N
    current = 0
    for i in range(N):
        current += diff[i]
        count[i] = current
    
    # Points for each tree = number of fruits × harvest count
    result = [A[i] * count[i] for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.5opus.