Overview

Given the inventory counts of \(N\) stores, we perform \(Q\) operations of “rewriting the inventory of a specific store.” After each operation, we need to find the total inventory across all stores.

Analysis

The simplest approach would be to loop through all stores and sum up their inventories after each update query. However, let’s consider the computational complexity of this naive simulation approach.

• For each update, summing \(N\) elements takes \(O(N)\) time.
• Since there are \(Q\) queries, the overall complexity is \(O(NQ)\).

Given the constraints of this problem where \(N, Q \le 2 \times 10^5\), \(N \times Q\) can be as large as approximately \(4 \times 10^{10}\). Under typical online judge time limits (around 2 seconds), the rough guideline is that about \(10^8\) operations can be processed per second, so this approach will not be fast enough (resulting in TLE: Time Limit Exceeded).

Therefore, we need the technique of “computing only the difference from the previous total.” When a store’s inventory changes from \(A_{old}\) to \(A_{new}\), the change in the overall total is \(A_{new} - A_{old}\). In other words, $\(\text{new total} = \text{current total} - \text{old inventory} + \text{new inventory}\)\( By performing this calculation, we can obtain the new total with just a few operations (\)O(1)\() without having to re-examine all \)N$ stores.

Algorithm

1. First, compute the sum of the given \(A_1, A_2, \ldots, A_N\) and store it in a variable current_total.
2. For each query \((X_j, Y_j)\), perform the following:
   • Check the current inventory \(A_{X_j}\) of store \(X_j\) before the update.
   • Add the difference \((Y_j - A_{X_j})\) to current_total.
   • Update the array value (\(A_{X_j} = Y_j\)).
   • Output the current current_total.

Complexity

• Time complexity: \(O(N + Q)\)
  • The initial sum computation takes \(O(N)\), and each query is processed in \(O(1)\), so the overall complexity is \(O(N + Q)\). This amounts to approximately \(2 \times 10^5 + 2 \times 10^5 = 4 \times 10^5\) operations, which is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array that holds the current inventory of each store.

Implementation Notes

• 1-indexed vs 0-indexed: The problem statement gives store numbers from \(1\) to \(N\), but arrays (lists) in programs typically start from \(0\), so you need to subtract \(1\) from the index when accessing the array.

• Fast I/O: In Python, when the number of inputs or outputs is large (exceeding \(10^5\)), you can significantly reduce execution time by reading all input at once with sys.stdin.read().split() instead of calling input() repeatedly, or by using sys.stdout.write() for batch output.

  Source Code

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

This editorial was generated by gemini-3-flash-preview.