概要

複数回の「区間に一斉に \(K\) を足す」操作をすべて反映した後の配列 \(C\) を、効率よく求める問題です。

考察

各水やりは区間 \([L_j, R_j]\) の全要素に \(K\) を加算します。素朴に各クエリごとに区間をループして足すと、最悪で
\(Q \times N \approx 2\times 10^5 \times 2\times 10^5 = 4\times 10^{10}\) 回更新になり、時間内に終わりません（TLE）。

重要な観察は、「各花壇 \(i\) に最終的に加わる量は、\(i\) を含む区間クエリの回数 \(\times K\) である」という点です。
つまり、まず「各位置が何回水やり対象になったか（回数）」を高速に数えられれば、最後にまとめて \(C_i + (\text{回数})\times K\) とできます。

ここで使えるのが 差分配列（いもす法） です。区間加算の回数を、端点だけの更新で記録し、最後に累積和で復元します。

例として \(N=5\)、クエリが \([2,4]\)（1-indexed）1回だけだとすると、 - 2番目から回数が +1 され - 5番目（= 4の次）から回数が元に戻る（-1）
という情報だけ持てば十分です。これを累積すると各位置の回数が得られます。

アルゴリズム

1. 長さ \(N+1\) の配列 diff を用意し、すべて \(0\) で初期化する（差分配列）。
2. 各クエリ \((L, R)\) について（入力は1-indexed）:
   • 0-indexed に直して L -= 1
   • diff[L] += 1（\(L\) から「回数 +1」を開始）
   • もし \(R < N\) なら diff[R] -= 1（\(R\) は 1-indexed の右端なので、0-indexed では「\(R\) の次」位置が index \(R\) になる）
3. diff の累積和を左から取り、各位置 \(i\) の「水やり回数」cnt を得る。
4. 各 \(i\) について \(C_i \leftarrow C_i + cnt \times K\) と更新する。
5. 更新後の \(C\) を出力する。

（コードでは cnt を逐次更新していくことで累積和を計算しています。）

計算量

• 時間計算量: \(O(N+Q)\)（各クエリは \(O(1)\)、最後に配列を1回走査）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 添字のずれ（1-indexed と 0-indexed） に注意します。コードでは L -= 1 だけ行い、右端側は「\(R\) の次」に相当する index がちょうど R になることを利用しています。

• diff を \(N+1\) にしておくと、境界処理を安全に書けます（ただしこのコードでは R < N のときだけ diff[R] -= 1 としている）。

• 増加量は最大で \(Q \times K\) なので \(2\times 10^5 \times 10^9 = 2\times 10^{14}\) 程度になります。Python の int なら問題ありません。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。