概要

\(N\) 個の店舗の在庫数が与えられ、「特定の店舗の在庫を書き換える」という操作を \(Q\) 回行います。各操作の直後に、全店舗の在庫の合計値を求める問題です。

考察

最も単純な方法は、各更新クエリのたびに全店舗の在庫をループで足し合わせることです。しかし、この方法（愚直なシミュレーション）では計算量がどうなるか考えてみましょう。

• 1回の更新につき、\(N\) 個の要素を合計するのに \(O(N)\) の時間がかかります。
• クエリは \(Q\) 回あるため、全体の計算量は \(O(NQ)\) となります。

本問題の制約では \(N, Q \le 2 \times 10^5\) であるため、\(N \times Q\) は最大で \(4 \times 10^{10}\) 程度になります。一般的なオンラインジャッジの制限時間（2秒程度）では、1秒間に処理できる計算量は \(10^8\) 回程度が目安であるため、この方法では間に合いません（TLE：実行時間制限超過となります）。

そこで、「前回の合計値との差分だけを計算する」という工夫が必要になります。 ある店舗の在庫が \(A_{old}\) から \(A_{new}\) に変わったとき、全体の合計値の変化は \(A_{new} - A_{old}\) です。 つまり、 $\(\text{新しい合計} = \text{現在の合計} - \text{元の在庫数} + \text{新しい在庫数}\)\( という計算を行えば、わざわざ \)N\( 個の店舗をすべて見直さなくても、わずか数回の計算（\)O(1)$）で新しい合計値を求めることができます。

アルゴリズム

1. 最初に与えられた \(A_1, A_2, \ldots, A_N\) の合計値を計算し、変数 current_total に保持します。
2. 各クエリ \((X_j, Y_j)\) に対して以下の処理を行います：
   • 更新前の店舗 \(X_j\) の在庫数 \(A_{X_j}\) を確認します。
   • current_total に差分 \((Y_j - A_{X_j})\) を加算します。
   • 配列の値を更新します（\(A_{X_j} = Y_j\)）。
   • その時点の current_total を出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • 最初の合計計算に \(O(N)\)、各クエリの処理に \(O(1)\) ずつかかるため、全体で \(O(N + Q)\) となります。これは \(2 \times 10^5 + 2 \times 10^5 = 4 \times 10^5\) 程度の計算量であり、十分に高速です。
• 空間計算量: \(O(N)\)
  • 各店舗の現在の在庫を保持するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 1-indexed と 0-indexed: 問題文では店舗番号が \(1\) から \(N\) で与えられますが、プログラムの配列（リスト）は通常 \(0\) から始まるため、インデックスを \(1\) 引いて管理する必要があります。

• 高速な入出力: Python の場合、入力の数や出力の数が多い（\(10^5\) を超える）ときは、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込んだり、sys.stdout.write() を使って一括で出力したりすることで実行時間を大幅に短縮できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリスト化します（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 店舗数 N と 更新回数 Q を取得
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 各店舗の初期在庫数 A をリストとして取得
    # 店舗番号は 1-indexed なので、プログラム内では 0-indexed に合わせるため注意します
    A = list(map(int, input_data[2:2+N]))
    
    # 現在の全店舗の在庫合計を計算
    current_total = sum(A)
    
    # 更新クエリの開始位置を特定
    cursor = 2 + N
    results = []
    
    # Q 回の更新処理を行う
    for _ in range(Q):
        # 更新する店舗番号 X (1-indexed) と 新しい在庫数 Y
        x_idx = int(input_data[cursor]) - 1
        y_val = int(input_data[cursor+1])
        cursor += 2
        
        # 在庫の差分を計算して合計値を更新
        # (新しい在庫数) - (現在の在庫数) を合計に加算する
        diff = y_val - A[x_idx]
        current_total += diff
        
        # 店舗の在庫データを更新
        A[x_idx] = y_val
        
        # 現在の合計を結果リストに追加
        results.append(str(current_total))
    
    # 全ての結果を改行区切りで一気に出力（高速化のため）
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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