Overview

This problem involves performing \(Q\) operations of “add \(K\) to all elements in the range \([L, R]\)” on an array of length \(N\), and finding the final state of the array.

Analysis

Naive Approach

The simplest method is, for each query \((L_j, R_j)\), to loop through and add \(K\) to each flower bed from the \(L_j\)-th to the \(R_j\)-th. However, in the worst case (when all queries cover the range \([1, N]\)), the time complexity becomes \(O(N \times Q)\). Given the constraints \(N, Q \leq 2 \times 10^5\), this would require up to approximately \(4 \times 10^{10}\) operations, far exceeding the time limit (typically around 2 seconds) and resulting in TLE.

Efficient Approach: Imos Method (Difference Array)

To efficiently handle the operation of “adding to a contiguous range all at once,” we use the “Imos method (difference array)”. Since the value \(K\) to be added is constant, we first count “how many times each flower bed was watered in total,” and then multiply that count by \(K\) and add it to the initial value \(C_i\).

Using the Imos method, a single range update \([L, R]\) can be recorded with just the following 2 point updates: 1. Add \(+1\) to diff[L] (watering starts here) 2. Add \(-1\) to diff[R + 1] (watering ends after this point)

After recording all queries, by taking the prefix sum of this array, we can compute the “number of waterings” for each position all at once in \(O(N)\).

Algorithm

1. Initialization: Prepare an array diff of size \(N+2\) to record the differences in watering counts for each flower bed, and initialize all values to 0.
2. Query Processing: For each watering \((L_j, R_j)\), update diff[L_j] += 1 and diff[R_j + 1] -= 1.
3. Prefix Sum Calculation: Compute the prefix sum of the array diff from left to right. The prefix sum value at position \(i\) directly represents the number of times the \(i\)-th flower bed was watered.
4. Final Result Calculation: For each flower bed \(i\), the final moisture level is C[i] + (number of waterings * K).

Complexity

• Time Complexity: \(O(N + Q)\)
  • Reading input takes \(O(N + Q)\), processing queries takes \(O(Q)\), and computing the prefix sum and outputting results takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array holding the moisture levels of the flower beds and the difference array.

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python we use sys.stdin.read().split() to read all input at once, reducing execution time.

• Index Management: The problem uses 1-indexed numbering (starting from 1), but Python lists are 0-indexed. By allocating the difference array diff slightly larger (\(N+2\)), we prevent out-of-bounds errors when accessing R+1, and can process everything intuitively using 1-indexed access.

• Bulk Output: By using the asterisk as in print(*(C)), we can efficiently output the list elements separated by spaces.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    # 大量の入力を処理する場合、sys.stdin.read().split() が高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 花壇の数, K: 1回の水やりでの増加量, Q: 水やりの回数
    N = int(input_data[0])
    K = int(input_data[1])
    Q = int(input_data[2])
    
    # C: 各花壇の初期の水分量 (0-indexed)
    C = list(map(int, input_data[3:3+N]))
    
    # 差分配列（いもす法）を用いて範囲更新を効率的に行います。
    # diff[i] は i番目と i-1番目の花壇への水やり回数の差を記録します。
    # 花壇の番号は 1 から N までなので、サイズ N+2 の配列を用意します。
    diff = [0] * (N + 2)
    
    # 水やりの範囲情報を取得し、差分配列を更新します。
    # 各範囲 [L, R] に対して L 番目に +1、R+1 番目に -1 します。
    idx = 3 + N
    for _ in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        diff[L] += 1
        diff[R + 1] -= 1
        idx += 2
        
    # 差分配列の累積和をとることで、各花壇が合計何回水やりされたかを求めます。
    # 累積和を計算しながら、元の水分量 C に (回数 * K) を加算します。
    current_watering_count = 0
    for i in range(1, N + 1):
        current_watering_count += diff[i]
        # i番目の花壇は C[i-1] に対応します。
        C[i-1] += current_watering_count * K
    
    # 結果をスペース区切りで出力します。
    print(*(C))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.