Overview

This is a problem of efficiently computing the array \(C\) after applying multiple “add \(K\) to an entire interval” operations.

Analysis

Each watering adds \(K\) to all elements in the interval \([L_j, R_j]\). Naively looping through the interval for each query and adding would result in at most
\(Q \times N \approx 2\times 10^5 \times 2\times 10^5 = 4\times 10^{10}\) updates, which will not finish in time (TLE).

The key observation is that “the total amount added to each flower bed \(i\) is the number of interval queries containing \(i\), multiplied by \(K\).”
In other words, if we can quickly count “how many times each position was targeted for watering (count),” we can compute \(C_i + (\text{count})\times K\) all at once at the end.

The technique we can use here is the difference array (imos method). We record the interval addition counts by updating only the endpoints, then reconstruct the values using a prefix sum at the end.

For example, if \(N=5\) and there is only one query \([2,4]\) (1-indexed): - The count increases by +1 starting from position 2 - The count returns to its original value (-1) starting from position 5 (= the position after 4)
It is sufficient to store just this information. Taking the prefix sum gives the count at each position.

Algorithm

1. Prepare an array diff of length \(N+1\), initialized to all \(0\) (difference array).
2. For each query \((L, R)\) (input is 1-indexed):
   • Convert to 0-indexed: L -= 1
   • diff[L] += 1 (start “+1 to count” from \(L\))
   • If \(R < N\), then diff[R] -= 1 (since \(R\) is the right endpoint in 1-indexed, in 0-indexed the “next position after \(R\)” has index \(R\))
3. Take the prefix sum of diff from left to right to obtain the “watering count” cnt for each position \(i\).
4. For each \(i\), update \(C_i \leftarrow C_i + cnt \times K\).
5. Output the updated \(C\).

(In the code, the prefix sum is computed by incrementally updating cnt.)

Complexity

• Time complexity: \(O(N+Q)\) (each query is \(O(1)\), followed by a single pass through the array)
• Space complexity: \(O(N)\) (difference array)

Implementation Notes

• Be careful about index shifts (1-indexed vs. 0-indexed). In the code, only L -= 1 is performed, and for the right endpoint, we take advantage of the fact that the index corresponding to “the position after \(R\)” is exactly R.

• Setting diff to size \(N+1\) allows boundary handling to be written safely (though in this code, diff[R] -= 1 is only done when R < N).

• The maximum increase can be as large as \(Q \times K\), which is around \(2\times 10^5 \times 10^9 = 2\times 10^{14}\). This is not a problem with Python’s int.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, K, Q = map(int, input().split())
    C = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(Q):
        L, R = map(int, input().split())
        L -= 1
        diff[L] += 1
        if R < N:
            diff[R] -= 1

    cnt = 0
    for i in range(N):
        cnt += diff[i]
        C[i] += cnt * K

    print(" ".join(map(str, C)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.