Overview

For each interval, count the number of harvests for trees within that interval, and compute the cumulative harvest points as the product of each tree’s fruit count and its harvest count.

Analysis

In this problem, we are given \(M\) days of harvest information (each being an interval \([L_j, R_j]\)), and we need to process “increment the harvest count by 1” for every tree within each interval. Ultimately, the harvest points for each tree \(i\) are “\(A_i \times (\text{harvest count})\)”.

What about a naive approach?

The most straightforward method is to increment the counter for every tree in the interval \([L_j, R_j]\) for each day. However, since the interval length can be up to \(N\) and the number of days can be up to \(2 \times 10^5\), this would require up to approximately \(2 \times 10^{10}\) operations in total, which would not fit within the time limit (typically around 1 second) and result in TLE.

What is an efficient approach?

This is where the “imos method” comes in. This is a technique for efficiently performing range addition operations, utilizing difference updates combined with prefix sums.

Idea behind the imos method:

• For each interval \([L, R]\) addition, instead of uniformly adding to the entire interval, we only record the differences in a difference array diff:
  • diff[L] += 1
  • diff[R+1] -= 1
• Finally, by computing the prefix sum, we obtain the actual value added to each element.

With this method, each query can be processed in constant time, and we only need to compute the prefix sum once at the end, so the entire problem can be solved in \(O(N + M)\).

Algorithm

1. Read input efficiently (using sys.stdin.read).
2. For each day \(j\)’s harvest interval \([L_j, R_j]\), update the difference array diff (imos method).
3. Compute the prefix sum of diff to obtain the harvest count count[i] for each tree.
4. The harvest points for each tree are computed as \(A_i \times \text{count}[i]\).
5. Output the result.

Complexity

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

Implementation Notes

• The input indices are 1-indexed, so they need to be converted to 0-indexed for internal processing.

• The difference array diff should have size \(N+1\) to prevent out-of-bounds access.

• In Python, using fast input (sys.stdin.read) is necessary to avoid TLE.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx]) - 1   # 0-indexed
        R = int(data[idx+1]) - 1
        idx += 2
        diff[L] += 1
        diff[R+1] -= 1
    
    # 差分を累積和して、各木の収穫回数を求める
    count = [0] * N
    c = 0
    for i in range(N):
        c += diff[i]
        count[i] = c
    
    # 収穫ポイント = 果物の数 × 収穫回数
    points = [A[i] * count[i] for i in range(N)]
    
    print(' '.join(map(str, points)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.