Overview

Given a row of flower beds, the problem asks you to water specified intervals multiple times and determine the final moisture level of each bed.

Analysis

In this problem, if we directly update the moisture level of every flower bed within each interval, the worst case requires \(O(NQ)\) computations, which will result in TLE given the large constraints.

For example, naively performing the watering operation on interval \([L_j, R_j]\) would update up to \(N\) elements each time, which is inefficient.

Instead, we use a technique called the difference array (imos method). This is a preprocessing technique for efficiently performing uniform additions over intervals.

Specifically, by recording \(+K\) at the start of the interval and \(-K\) at the position right after the end, we can later compute the prefix sum to determine how many times each element was added to. This allows us to process all \(Q\) operations efficiently.

Algorithm

1. For each watering interval \([L_j, R_j]\), add \(K\) to position \(L_j\) in the difference array diff, and add \(-K\) at position \(R_j+1\) to cancel the effect (converting to 0-indexed).
2. Compute the prefix sum of the difference array to determine how many times each flower bed was watered (i.e., the increase in moisture).
3. The final answer is the initial moisture level plus the accumulated increase.

For example, with \(N=5\), \(K=10\), and watering interval \([2, 4]\): - diff[1] += 10 - diff[4] -= 10

After computing the prefix sum, only the interval \([1, 3]\) (0-indexed) has \(10\) added to it.

Complexity

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

Implementation Notes

• The intervals are given in 1-indexed format, so don’t forget to convert to 0-indexed.
• Set the size of the difference array to \(N+1\) to simplify boundary handling.
• When computing the prefix sum at the end, it is efficient to update while carrying over the previous value.

## Source Code

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

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    C = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexedにする
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        
        diff[L] += K
        diff[R + 1] -= K
    
    # 差分配列から実際の追加分を計算
    added = [0] * N
    current = 0
    for i in range(N):
        current += diff[i]
        added[i] = current
    
    # 最終的な水分量を計算
    result = [C[i] + added[i] for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

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