Overview

This problem asks you to determine the moisture level of each section of a flower bed after performing \(M\) operations, each of which uniformly adds (or drains) water across an entire interval. By using the imos method (the inverse operation of prefix sums), we can efficiently handle range addition operations.

Analysis

Naive Approach and Its Issues

For each task \(j\), if we iterate from section \(L_j\) to \(R_j\) and add \(D_j\) to each, a single task takes up to \(O(N)\) time. With \(M\) tasks, the total complexity is \(O(NM)\). When both \(N\) and \(M\) are up to \(2 \times 10^5\), we get \(O(NM) = O(4 \times 10^{10})\), which will not finish within the time limit.

Key Insight

Each task is an operation that “adds the same value to a contiguous range of sections.” When performing a large number of such uniform range additions and wanting to know the final result all at once, the imos method is extremely effective.

Using the imos method, each range addition can be recorded in \(O(1)\), and after recording all tasks, computing a single prefix sum reveals the addition results for all sections.

Algorithm

How the Imos Method Works

Prepare a difference array diff of length \(N+1\), initialized entirely to \(0\).

The operation of adding \(D\) to sections \(L\) through \(R\) is recorded in the difference array as follows:

• diff[L-1] += D (the effect starts from section \(L\))
• diff[R] -= D (the effect disappears starting from the section after \(R\))

Concrete example: For \(N = 5\), adding \(+3\) to sections \(2\) through \(4\):

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

Taking the prefix sum of this difference array:

prefix: [0, +3, +3, +3, 0, 0]

We can see that \(+3\) has been added only to sections \(2, 3, 4\).

Overall Procedure

1. Initialize the difference array diff with \(N+1\) elements
2. For each of the \(M\) tasks, record diff[L_j - 1] += D_j and diff[R_j] -= D_j
3. Compute the prefix sum of diff from the beginning, adding the result to the initial value \(A_i\)
4. Output the results

Complexity

• Time complexity: \(O(N + M)\)
  • Recording to the difference array: \(O(1)\) per task × \(M\) tasks = \(O(M)\)
  • Computing the prefix sum and adding to initial values: \(O(N)\)
• Space complexity: \(O(N)\)
  • \(N+1\) elements for the difference array diff

Implementation Notes

• 1-indexed to 0-indexed conversion: The problem uses sections starting from \(1\), but arrays start from \(0\), so we add to diff[L-1] and subtract at diff[R]. By making the difference array have \(N+1\) elements, we prevent out-of-bounds access when \(R = N\).

• Fast input: Since \(N\) and \(M\) can be large, reading all input at once using sys.stdin.buffer.read() and then splitting is a faster approach.

• Integer range: The moisture level of each section can reach up to \(10^{18}\), but Python natively supports arbitrary-precision integers, so there is no concern about overflow (in C++ and similar languages, you would need to use long long).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    A = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # imos法
    diff = [0] * (N + 1)
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L - 1] += D
        diff[R] -= D
    
    current = 0
    for i in range(N):
        current += diff[i]
        A[i] += current
    
    sys.stdout.write(' '.join(map(str, A)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.