Overview

This problem asks you to perform \(Q\) operations, each adding the same value \(C_i\) to the interval \([L_i, R_i]\), and then output the total value at each position.

Analysis

If we naively implement “add \(C_i\) to all planters from \(L_i\) to \(R_i\)” for each day, a single operation may update up to \(N\) elements, resulting in \(O(NQ)\) in the worst case.
Given the constraints \(N, Q \le 2 \times 10^5\), \(NQ\) can be as large as \(4 \times 10^{10}\), which will not finish in time (TLE).

The key insight here is that “bulk addition to an interval” can be handled by recording only the differences (boundaries of change).

For example, “add \(C\) to interval \([L, R]\)” can be thought of as: - From \(L\) onward, there is an increase of \(+C\) - But from \(R+1\) onward, cancel the increase with \(-C\)

In other words, prepare an array diff and simply do: - diff[L] += C - diff[R+1] -= C

Then, by taking the prefix sum from left to right at the end, we can recover the total for each planter.

Algorithm

1. Initialize a difference array diff of length \(N+2\) with \(0\) (extra space to safely handle \(R+1\)).
2. For each query \((L, R, C)\), do the following:
   • diff[L] += C
   • diff[R+1] -= C
3. Set cur = 0 and iterate \(i\) from \(1\) to \(N\):
   • cur += diff[i]
   • This is the final water amount for planter \(i\)
4. Output the resulting \(N\) values.

Concrete Example

For \(N=5\) and the operation “add \(+3\) to \([2,4]\)”: - diff[2] += 3, diff[5] -= 3

Taking the prefix sum of diff:
Position 1: 0
Position 2: 3
Position 3: 3
Position 4: 3
Position 5: 0
We can see that only the interval is correctly increased.

Complexity

• Time complexity: \(O(N + Q)\) (each query is \(O(1)\), and the final prefix sum is \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array and result array)

Implementation Notes

• Since we update diff[R+1], we set the array size to N+2 to avoid out-of-bounds access.

• Since the input can be large, fast input methods like sys.stdin.buffer.read() are effective in Python.

• In this code, we use 1-indexed processing, and only the output array is packed as 0-indexed (res[i-1] = cur).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, Q = data[0], data[1]
    diff = [0] * (N + 2)
    idx = 2
    for _ in range(Q):
        L = data[idx]; R = data[idx + 1]; C = data[idx + 2]
        idx += 3
        diff[L] += C
        diff[R + 1] -= C

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

    sys.stdout.write(" ".join(map(str, res)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.