概要

\(N\) 店舗の在庫数が与えられ、\(Q\) 回の在庫更新のたびに全店舗の在庫合計を求める問題。

考察

この問題では、各更新のたびに「全店舗の在庫合計」を求めることになります。素朴な方法として、毎回全ての在庫数を足し直すことを考えると、計算量は \(O(Q \times N)\) となり、最大で \(4 \times 10^{10}\) 回の計算が必要になり、時間内に収まりません（TLE）。

しかし、よく考えると毎回全店舗の合計を再計算する必要はありません。必要なのは「1つの店舗の在庫がどれだけ増えた（または減った）か」だけです。つまり、全体の合計を持っておき、「古い在庫数を引いて、新しい在庫数を足す」ことで、効率的に最新の合計を維持できます。

例えば、初期在庫が \([3, 1, 4]\) で合計が \(8\) だったとします。ここで店舗2の在庫が \(1\) から \(5\) に変更された場合、差分は \(5 - 1 = 4\) なので、全体の合計も \(8 + 4 = 12\) に更新できます。このように、差分更新を利用することで、毎回 \(O(1)\) で答えが求められます。

アルゴリズム

1. 最初に全店舗の在庫数の合計 \(total\) を計算して保持しておく。
2. 各更新において：
   • 変更される店舗 \(X\) の現在の在庫数 \(A[X]\) を取得。
   • 新しい在庫数 \(Y\) との差分を \(total\) に反映：
     $\(total = total - A[X] + Y\)$
   • 店舗 \(X\) の在庫数を \(Y\) に更新：
     $\(A[X] = Y\)$
   • 現在の \(total\) を出力。

この方法により、毎回の更新と出力が定数時間で可能になります。

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期合計計算が \(O(N)\)、各クエリ処理が \(O(1)\) で \(Q\) 回繰り返すため。
• 空間計算量: \(O(N)\)
  • 各店舗の在庫数を保持する配列 \(A\) のサイズ。

実装のポイント

• 店舗番号が1-indexedで入力されるので、内部では0-indexedに変換すること（X -= 1）。
• 差分更新の順序に注意：まず合計を更新してから、配列の値を書き換える。

## ソースコード

```python
# 在庫管理システムの解答コード

# 入力の読み込み
N, Q = map(int, input().split())
A = list(map(int, input().split()))

# 初期在庫数の合計を計算
total = sum(A)

# 各更新処理
for _ in range(Q):
    X, Y = map(int, input().split())
    # 1-indexed から 0-indexed へ変換
    X -= 1
    
    # 合計から古い値を引き、新しい値を足す
    total = total - A[X] + Y
    # 在庫数を更新
    A[X] = Y
    
    # 更新後の合計を出力
    print(total)

この解説は qwen3-coder-480b によって生成されました。