Overview

Given the initial moisture level of each section, we perform multiple range addition operations to determine the final moisture level of each section.

Analysis

In this problem, each section has an initial value \(A_i\), and we need to find the result after applying \(M\) range update operations (adding \(D_j\) to the interval \([L_j, R_j]\)).

The naive approach is insufficient

If we actually update all elements in the interval \([L_j, R_j]\) for each operation, each operation takes \(O(N)\) in the worst case, resulting in an overall time complexity of \(O(NM)\).
Given the constraints, \(N, M\) can be up to \(2 \times 10^5\), so \(O(NM)\) would require up to \(4 \times 10^{10}\) computations, which clearly exceeds the time limit (TLE).

Speeding up with difference arrays

Operations that “uniformly add to an interval” can be efficiently handled using techniques such as the imos method (difference array), BIT (Fenwick Tree), or lazy segment trees.
Here, we use the idea of the imos method: we record addition and subtraction events at the start and end+1 of each interval, then take a prefix sum afterwards to obtain the total change for each section.

Specifically: - The operation of adding \(D\) to the interval \([L, R]\) is recorded as an event of \(+D\) at position \(L\) and \(-D\) at position \(R+1\). - Finally, we scan from left to right, maintaining a running total of the current change, and add it to the initial value to obtain the answer.

This allows each operation to be processed in constant time, solving the entire problem in \(O(N + M)\).

Algorithm

1. For each operation \(j\), record the information of adding \(D_j\) to the interval \([L_j, R_j]\) as differences:

   • \(+D_j\) at position \(L_j\)
   • \(-D_j\) at position \(R_j + 1\)

2. For each position \(i\), compute the running total of differences that should be added up to that point (using the imos method).

3. The final moisture level of each section is the initial value \(A_i\) plus the cumulative sum of differences at that section.

This can be implemented using preprocessing on an array and prefix sum computation, without the need for a BIT.

Complexity

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

Implementation Notes

• Convert the operation information (\(L, R, D\)) into an event list during preprocessing, recording additions and subtractions at the start position and end position + 1.
• Build the answer by maintaining the current cumulative change (like a prefix sum) and adding it to the initial values.
• In Python, use fast input processing (such as sys.stdin.read) to handle large inputs efficiently.

## Source Code

```python
import sys
input = sys.stdin.read

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def add(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & -i
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

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 = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(data[idx])
        idx += 1
    
    # 座標圧縮のためのイベントリスト
    events = []
    for i in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        events.append((L, D))
        events.append((R+1, -D))
    
    # BITの準備
    bit = BIT(N)
    
    # 各作業を処理
    # イベントをソートして処理する
    # しかし、ここでは直接差分をBITに載せる
    
    # 初期化: 各位置への加算クエリを記録
    updates = [[] for _ in range(N+2)]
    idx = 2 + N
    for j in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        updates[L].append(D)
        updates[R+1].append(-D)
    
    result = [0] * (N+1)
    current = 0
    for i in range(1, N+1):
        for d in updates[i]:
            current += d
        result[i] = A[i] + current
    
    print(' '.join(map(str, result[1:])))

if __name__ == "__main__":
    main()

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