概要

各店舗の在庫数が「1点更新（代入）」されるたびに、全店舗の在庫合計を素早く更新して出力する問題です。

考察

更新のたびに全店舗の合計を求め直す（例：毎回 \(\sum A_i\) を計算する）素朴な方法だと、1回の更新に \(O(N)\) かかります。すると全体で \(O(NQ)\) となり、制約最大の \(N,Q \le 2\times 10^5\) では \(4\times 10^{10}\) 回規模になってしまい、時間内に終わりません（TLE）。

重要な気づきは、「合計値は差分だけ更新できる」ということです。

例えば、ある店舗 \(x\) の在庫が \(A_x\) から \(y\) に変わるとき、全体の合計は - 古い \(A_x\) が合計から消えて - 新しい \(y\) が合計に加わる

ので、合計の変化量は \(y - A_x\) です。したがって、 - total += y - A[x] とすれば、合計を \(O(1)\) で更新できます。

このためには、各店舗の現在値 \(A[x]\) を常に保持しておく必要があります（次の更新で「古い値」を参照するため）。

アルゴリズム

1. 初期配列 \(A\) を読み込み、初期合計 \(total=\sum_{i=1}^N A_i\) を計算する。
2. 各更新 \((X_j, Y_j)\) について：
   • 0-index に直して \(x = X_j - 1\) とする。
   • 合計を差分更新：\(total \leftarrow total + (Y_j - A_x)\)
   • 配列を更新：\(A_x \leftarrow Y_j\)
   • \(total\) を出力する。

（例） - \(A=[3,1,4]\) で合計 \(total=8\) - 店舗2を \(1 \to 10\) に変更すると、差分は \(10-1=9\) - 新しい合計は \(8+9=17\)

計算量

• 時間計算量: \(O(N+Q)\)（初期合計に \(O(N)\)、各更新は \(O(1)\)）
• 空間計算量: \(O(N)\)（配列 \(A\) を保持）

実装のポイント

• 入力の店舗番号 \(X_j\) は \(1\) 始まりなので、Pythonの配列に合わせて x -= 1 が必要です。

• 合計は最大で \(N \times 10^9\) 程度になり得ますが、Pythonの int は任意精度なのでオーバーフローの心配はありません（他言語なら 64-bit 整数を使う）。

• 出力を高速化するため、各答えをリストに溜めて最後に "\n".join(...) でまとめて出力しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)

    out_lines = []
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        total += y - A[x]
        A[x] = y
        out_lines.append(str(total))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

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