Overview

This is a problem where each section of a flower bed has an initial moisture level, and we need to find the final moisture level of each section after performing multiple range updates (watering or draining).

Analysis

A naive approach would directly add \(D_j\) to each section in the interval \([L_j, R_j]\) for each operation. However, since \(N\) and \(M\) can be as large as \(2 \times 10^5\), a single operation may require up to \(2 \times 10^5\) additions, totaling \(M \times (R_j - L_j + 1)\) operations, which in the worst case amounts to \(4 \times 10^{10}\) computations. This clearly exceeds the time limit.

To achieve efficient range updates, we can use a difference array technique, which can be thought of as a form of “lazy evaluation” or the “inverse operation of prefix sums.” By recording each operation as a difference and computing the prefix sum only once at the end, we can process range updates efficiently.

Algorithm

1. Create a difference array: Prepare an array diff of length \(N+1\), initialized to all zeros.
2. Record operations as differences: For each operation \((L_j, R_j, D_j)\):
   • diff[L_j-1] += D_j
   • diff[R_j] -= D_j (if \(R_j\) is not the last section)
3. Compute prefix sums: Calculate the prefix sum from the beginning of the diff array. This gives the total water amount added to each section.
4. Compute results: Add the accumulated amount obtained from the prefix sum to the initial value \(A_i\) to get the final moisture level.

With this approach, each operation is processed in constant time \(O(1)\), and the final prefix sum computation completes in \(O(N)\), making it very efficient.

Complexity

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

Implementation Notes

• Be careful with array indexing: The problem uses 1-indexed section numbers, but the code processes them as 0-indexed, so L_j-1 is used as the index.

• Preventing out-of-bounds access: When \(R_j\) is the last section (\(N\)), the subtraction at diff[R_j] is unnecessary (since the array size is \(N+1\), index \(N\) is within bounds, but semantically it is not needed). The code checks this with if R < N:.

• Bulk input reading: To handle large inputs, sys.stdin.read is used for bulk reading to improve performance.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    A = list(map(int, data[idx:idx+N])); idx += N
    
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]); R = int(data[idx+1]); D = int(data[idx+2]); idx += 3
        diff[L-1] += D
        if R < N:
            diff[R] -= D
            
    current = 0
    result = []
    for i in range(N):
        current += diff[i]
        result.append(str(A[i] + current))
        
    print(" ".join(result))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.