概要

店舗の在庫が更新されるたびに、全店舗の在庫合計を効率的に求める問題です。

考察

素朴なアプローチとその問題点

最も単純な方法は、毎回の更新後に全店舗の在庫を足し合わせて合計を計算することです。

# 素朴なアプローチ（TLEになる）
for 各更新:
    在庫を更新
    total = sum(A)  # 毎回 O(N) かかる
    print(total)

しかし、この方法では： - 1回の合計計算に \(O(N)\) かかる - \(Q\) 回の更新があるので、全体で \(O(N \times Q)\) - \(N, Q\) が最大 \(2 \times 10^5\) なので、\(4 \times 10^{10}\) 回の計算が必要 - これは制限時間に間に合いません（TLE）

重要な気づき

毎回の更新では 1つの店舗の在庫しか変わらない ことに注目します。

例えば、店舗3の在庫が \(50\) から \(80\) に変わった場合： - 全体の合計は \(80 - 50 = 30\) だけ増える - 他の店舗の在庫は変わらないので、それらを毎回足し直す必要はない

つまり、差分だけを更新すれば \(O(1)\) で新しい合計が求められます。

アルゴリズム

1. 前処理: 最初に全店舗の在庫合計 total を計算する
2. 各更新時:
   • 店舗 \(X\) の古い在庫値を A[X-1] で取得
   • 合計を更新: total = total - (古い値) + (新しい値)
   • 配列を更新: A[X-1] = 新しい値
   • 更新後の total を出力

具体例

\(N = 3\), 初期在庫が \(A = [10, 20, 30]\) の場合：

• 初期合計: \(total = 10 + 20 + 30 = 60\)

更新1: 店舗2の在庫を50に変更 - 古い値: \(A[1] = 20\) - \(total = 60 - 20 + 50 = 90\) - \(A = [10, 50, 30]\) - 出力: 90

更新2: 店舗1の在庫を0に変更 - 古い値: \(A[0] = 10\) - \(total = 90 - 10 + 0 = 80\) - \(A = [0, 50, 30]\) - 出力: 80

計算量

• 時間計算量: \(O(N + Q)\)
  • 初期合計の計算: \(O(N)\)
  • 各更新処理: \(O(1)\) × \(Q\) 回 = \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 在庫を保持する配列のサイズ

実装のポイント

1. 1-indexed と 0-indexed の変換

   • 問題では店舗番号が1から始まる（1-indexed）
   • Pythonの配列は0から始まる（0-indexed）
   • idx = X - 1 で変換が必要

2. オーバーフローに注意

   • 各在庫は最大 \(10^9\)、店舗数は最大 \(2 \times 10^5\)
   • 合計は最大 \(2 \times 10^{14}\) 程度になりうる
   • Pythonでは整数のオーバーフローがないため問題なし（C++などでは long long が必要）

3. 高速な入力

   • sys.stdin.readline を使うことで、大量の入力を高速に読み込める

     ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    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())
        # 店舗Xは1-indexedなので、配列のインデックスはX-1
        idx = X - 1
        # 合計から古い値を引いて新しい値を足す
        total = total - A[idx] + Y
        # 在庫を更新
        A[idx] = Y
        print(total)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。