Overview

Given \(N\) planters and \(Q\) operations, each specifying a range to water, find the total amount of water given to each planter at the end.

Analysis

In this problem, each query repeats the operation of “adding the same value to all elements in a certain range.” For example, the operation of watering \(C\) liters to each planter from \(L\) to \(R\) corresponds to adding \(C\) to all elements from index \(L-1\) to \(R-1\) in the array (converting to 0-indexed).

A naive approach would be to “actually add the value to the range for each query.” However, in the worst case, this method requires updating up to \(N\) elements per query, resulting in an overall time complexity of \(O(NQ)\). Since the constraints are \(N, Q \leq 2 \times 10^5\), this cannot be processed within the time limit (requiring on the order of \(10^{10}\) computations).

This is where the technique called “difference array (imos method)” comes in. By using a difference array, uniform addition over a range can be processed in constant time.

For example, the operation of adding value \(C\) to all elements in the range \([L, R]\) of array \(A\) can be expressed using a difference array \(diff\) as follows: - \(diff[L] \mathrel{+}= C\) - \(diff[R+1] \mathrel{-}= C\)

Then, by taking the prefix sum of \(diff\), we can obtain the original array.

Using this method, each query can be processed in \(O(1)\), and the final prefix sum step takes \(O(N)\), so the overall time complexity is \(O(N + Q)\).

Algorithm

1. Prepare an array diff of size \(N+1\) (since we handle it in 1-indexed fashion, we allocate one extra element for boundary handling).
2. For each query \((L_i, R_i, C_i)\), record the differences as follows:
   • diff[L_i - 1] += C_i
   • diff[R_i] -= C_i
3. Take the prefix sum of diff to calculate the amount of water given to each planter.

Complexity

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

Implementation Notes

• sys.stdin.read() is used for fast input reading (important in Python).

• Pay attention to index management of the difference array: convert 1-indexed input to 0-indexed.

• When taking the prefix sum at the end, it is efficient to store the results in a list and output them all at once separated by spaces.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    index = 2
    for _ in range(Q):
        L = int(data[index])
        R = int(data[index+1])
        C = int(data[index+2])
        index += 3
        
        # 1-indexed なので、0-indexed に変換
        diff[L-1] += C
        diff[R] -= C
    
    # 差分配列から元の配列を構築
    result = []
    current = 0
    for i in range(N):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

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