Overview

This is a problem where we perform \(M\) range updates (harvests) on \(N\) trees and find the cumulative points for each tree at the end. The points for each tree can be calculated as “(number of fruits on that tree) \(\times\) (number of times that tree was harvested)”.

Analysis

Naive Approach and Its Limitations

One approach is to iterate through each tree from \(L_j\) to \(R_j\) for each day’s harvest operation and add points one by one. However, in the worst case, this method processes all \(N\) trees every day, resulting in a time complexity of \(O(N \times M)\). Given the constraints of this problem where \(N, M \le 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which exceeds the time limit.

Efficient Approach

For each tree \(i\), the final harvest points \(P_i\) can be expressed as: $\(P_i = A_i \times (\text{number of times tree } i \text{ was harvested})\)$

Since \(A_i\) is determined from the start, the problem can be solved if we can efficiently count “how many times each tree was harvested in total”. For performing operations that add a value to an entire range at once efficiently, the “imos method (difference array)” is extremely effective.

Algorithm

Procedure Using the Imos Method

1. Prepare the difference array: Initialize an array diff of length \(N+2\) with \(0\).
2. Record range updates: For each harvest range \([L_j, R_j]\), perform the following operations:
   • Add \(1\) to diff[L_j]
   • Subtract \(1\) from diff[R_j + 1]
3. Compute the prefix sum: By taking the prefix sum of the diff array, obtain the number of times \(C_i\) each tree \(i\) was harvested.
   • \(C_i = \sum_{k=1}^{i} \text{diff}[k]\)
4. Compute the final results: Calculate and output \(A_i \times C_i\) for each tree.

Using this method, each query (harvest operation) can be processed in \(O(1)\), and the final prefix sum computation takes only \(O(N)\), resulting in a significant speedup.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input, recording to the difference array (\(M\) times), computing the prefix sum (\(N\) times), and outputting results (\(N\) times) are all processed in linear time.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the arrays storing the number of fruits \(A_i\), the difference array, and the harvest counts.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python it is common to speed up I/O using sys.stdin.read().split() and sys.stdout.write().

• Index management: The problem statement is 1-indexed (trees 1 through \(N\)), so care must be taken with array handling within the program and the size of the difference array (accessing index \(R+1\)).

• Large numbers: Since \(A_i \le 10^9\) and \(M \le 2 \times 10^5\), the final points can be as large as about \(2 \times 10^{14}\). Python natively supports arbitrary-precision integers, so there is no concern about overflow.

  Source Code

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A_i の読み込み (0-indexedにするため、前にダミーを入れるかそのまま扱う)
    A = list(map(int, input_data[2:2+N]))
    
    # いもす法（差分配列）を用いて、各木が何回収穫されたかをカウントする
    # 1-indexedの範囲 [L, R] に対応するため、サイズ N+2 の配列を用意
    diff = [0] * (N + 2)
    
    ptr = 2 + N
    for _ in range(M):
        L = int(input_data[ptr])
        R = int(input_data[ptr+1])
        diff[L] += 1
        diff[R + 1] -= 1
        ptr += 2
        
    # 累積和をとり、各木の収穫回数 C_i を求める
    counts = [0] * (N + 1)
    current_count = 0
    for i in range(1, N + 1):
        current_count += diff[i]
        counts[i] = current_count
        
    # 各木の収穫ポイント P_i = A_i * C_i を計算
    results = []
    for i in range(N):
        # Aは0-indexedなので A[i]、countsは1-indexedなので counts[i+1]
        results.append(str(A[i] * counts[i+1]))
        
    # 結果をまとめて出力
    sys.stdout.write(" ".join(results) + "\n")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.