Overview

This problem asks us to process \(Q\) range addition queries and find the final total amount of water in each planter. It can be solved efficiently using the imos method (difference array).

Analysis

Problem with the Naive Approach

The simplest method is to add \(C_i\) to all elements in the range \([L_i, R_i]\) for each query.

for each query (L, R, C):
    for i = L to R:
        water[i] += C

However, this method requires up to \(O(N)\) operations per query. With \(Q\) queries, the total becomes \(O(NQ)\), and when \(N, Q\) are at most \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations, resulting in TLE (Time Limit Exceeded).

Solution: The Imos Method

By recording only the start and end points of uniform additions to a range, we can process each query in \(O(1)\).

Concrete Example: Adding 3 liters each to planters 2 through 4 (\(N = 5\))

Difference array operations: - diff[2] += 3 (start of range) - diff[5] -= 3 (one position after the end of range)

Difference array: [0, 0, +3, 0, 0, -3]

Taking the prefix sum: [0, 0, 3, 3, 3, 0]

→ We obtain the state where 3 has been added to planters 2, 3, and 4!

Algorithm

1. Prepare the difference array: Initialize an array diff of size \(N+2\) with zeros
2. Process queries: For each query \((L_i, R_i, C_i)\)
   • diff[L_i] += C_i (increase at the range start position)
   • diff[R_i + 1] -= C_i (decrease at the position after the range end)
3. Calculate prefix sum: Take the prefix sum of diff to compute the water amount for each planter

Illustration:

Query: L=2, R=4, C=3

diff:    [0] [0] [+3] [0] [0] [-3] [0]
index:    0   1    2   3   4    5   6

Prefix:  [0] [0] [ 3] [3] [3] [ 0] [0]
         ↑planter1  ↑2   ↑3  ↑4   ↑5

Complexity

• Time complexity: \(O(N + Q)\)
  • Initialization of difference array: \(O(N)\)
  • Processing each query: \(O(1) \times Q = O(Q)\)
  • Prefix sum calculation: \(O(N)\)
• Space complexity: \(O(N)\)
  • Size of difference array and result array

Implementation Notes

1. Array size: The size of diff should be \(N+2\). When \(R_i = N\), we access diff[R+1] = diff[N+1], so indices up to \(N+1\) are needed.

2. Handling 1-indexed: Since planters are numbered from 1 to \(N\), the prefix sum calculation runs from i = 1 to i = N.

3. Fast input: When \(Q\) is large, using sys.stdin.readline can speed up input processing.

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    
    # Using the imos method
    # diff[i] represents the change amount at position i
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L, R, C = map(int, input().split())
        diff[L] += C
        diff[R + 1] -= C
    
    # Calculate prefix sum to find the water amount for each planter
    result = []
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.