Overview

Count “how many times each tree was harvested” through the interval harvesting on each day, and finally multiply that count by the number of fruits \(A_i\) to obtain the total points.

Analysis

Each time a tree \(i\) is harvested, it always gains \(A_i\) points (since fruits do not decrease). Therefore, the final points are:

• Let \(C_i\) be the number of times tree \(i\) was harvested
• \(P_i = A_i \times C_i\)

If we naively increment the count by \(+1\) for every tree in \([L_j, R_j]\) on each day, in the worst case we perform an operation of interval length \(N\) a total of \(M\) times, resulting in a time complexity of \(O(NM)\) (up to approximately \(4 \times 10^{10}\)), which will certainly TLE.

Therefore, we need to efficiently process the “add +1 to an entire interval” operation. A typical approach is to use a difference array (imos method), which allows each interval update to be recorded in \(O(1)\), and then a prefix sum is taken at the end to obtain \(C_i\).

For example, with \(N=5\) and interval \([2,4]\), we record in the difference array diff: - diff[2] += 1 - diff[5] -= 1 (i.e., diff[R+1] -= 1)

Then, when we take the prefix sum of diff, only indices 2 through 4 will have their count incremented by +1.

Algorithm

1. Initialize a difference array diff of length \(N+2\) with zeros.
2. For each day \(j\)’s interval \([L_j, R_j]\):
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1
3. Compute the prefix sum sequentially from \(i=1\) to \(N\) as cur += diff[i], and let this be \(C_i\) (the harvest count for tree \(i\)).
4. For each tree, compute \(P_i = A_i \times C_i\) and output it.

Complexity

• Time complexity: \(O(N+M)\) (recording intervals is \(O(M)\), prefix sum and output is \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array and output)

Implementation Notes

• To handle diff[R+1], set the array size to N+2 to prevent out-of-bounds access.

• Since the input can contain more than \(4 \times 10^5\) elements, reading all at once with sys.stdin.buffer.read() is faster.

• Values can be at most \(A_i \le 10^9\) and \(C_i \le M \le 2 \times 10^5\), so the product can reach approximately \(2 \times 10^{14}\). Python’s int handles this safely.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    A = [next(it) for _ in range(N)]

    diff = [0] * (N + 2)
    for _ in range(M):
        L = next(it)
        R = next(it)
        diff[L] += 1
        diff[R + 1] -= 1

    res = []
    cur = 0
    for i in range(1, N + 1):
        cur += diff[i]
        res.append(str(A[i - 1] * cur))

    sys.stdout.write(" ".join(res))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.