概要

この問題は、長さ \(N\) の配列に対して「範囲 \([L, R]\) のすべての要素に \(K\) を加える」という操作を \(Q\) 回行い、最終的な配列の状態を求める問題です。

考察

素朴なアプローチ

最も単純な方法は、各クエリ \((L_j, R_j)\) ごとに、ループを回して \(L_j\) 番目から \(R_j\) 番目までの花壇に \(K\) を足していくことです。 しかし、最悪の場合（すべてのクエリが範囲 \([1, N]\) のとき）、計算量は \(O(N \times Q)\) となります。今回の制約では \(N, Q \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）を大幅に超えてしまいます（TLE）。

効率的なアプローチ：いもす法

「連続する範囲に一括で加算する」という操作を効率化するために、「いもす法（差分配列）」を利用します。 加算する値 \(K\) は一定であるため、まずは「各花壇が合計で何回水やりをされたか」を数え、最後にその回数に \(K\) を掛けて初期値 \(C_i\) に足す方針で考えます。

いもす法を用いると、1回の範囲更新 \([L, R]\) を以下の 2 点の更新だけで記録できます： 1. diff[L] に \(+1\) する（ここから水やりが始まる） 2. diff[R + 1] に \(-1\) する（ここを過ぎたら水やりが終わる）

すべてのクエリを記録した後、この配列の累積和をとることで、各地点の「水やり回数」を \(O(N)\) で一気に求めることができます。

アルゴリズム

1. 初期化: 各花壇の水やり回数の差分を記録する配列 diff をサイズ \(N+2\) で用意し、すべて 0 で初期化します。
2. クエリの処理: 各水やり \((L_j, R_j)\) に対して、diff[L_j] += 1、diff[R_j + 1] -= 1 と更新します。
3. 累積和の計算: 配列 diff を前から順番に累積和をとります。\(i\) 番目の累積和の値が、そのまま \(i\) 番目の花壇が水やりされた回数になります。
4. 最終結果の計算: 各花壇 \(i\) について、最終的な水分量は C[i] + (水やり回数 * K) となります。

計算量

• 時間計算量: \(O(N + Q)\)
  • 入力の読み込みに \(O(N + Q)\)、クエリの処理に \(O(Q)\)、累積和の計算と出力に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 花壇の水分量を保持する配列と、差分配列のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(Q\) が大きいため、Python では sys.stdin.read().split() を使って入力を一括で取得することで、実行時間を短縮しています。

• インデックスの管理: 問題文は 1-indexed（1番目から始まる）ですが、Python のリストは 0-indexed です。差分配列 diff を少し大きめに確保（\(N+2\)）しておくことで、R+1 のアクセスで範囲外エラーが出るのを防ぎ、1-indexed のまま直感的に処理できるようにしています。

• 一括出力: print(*(C)) のようにアスタリスクを使うことで、リストの要素をスペース区切りで効率よく出力できます。

  ソースコード

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

この解説は gemini-3-flash-preview によって生成されました。