Overview

Given the inventory counts of \(N\) stores, find the total inventory across all stores after each of \(Q\) inventory updates.

Analysis

In this problem, we need to compute the “total inventory across all stores” after each update. A naive approach of re-summing all inventory counts each time would have a time complexity of \(O(Q \times N)\), requiring up to \(4 \times 10^{10}\) operations, which will not finish in time (TLE).

However, upon closer thought, we don’t need to recalculate the total across all stores every time. All we need to know is “how much the inventory of one store increased (or decreased).” In other words, by maintaining a running total and “subtracting the old inventory count and adding the new inventory count,” we can efficiently keep the latest total up to date.

For example, suppose the initial inventories are \([3, 1, 4]\) with a total of \(8\). If store 2’s inventory changes from \(1\) to \(5\), the difference is \(5 - 1 = 4\), so the overall total can be updated to \(8 + 4 = 12\). By using this differential update approach, we can obtain the answer in \(O(1)\) each time.

Algorithm

1. First, compute and store the total \(total\) of all stores’ inventory counts.
2. For each update:
   • Retrieve the current inventory count \(A[X]\) of the store \(X\) being modified.
   • Reflect the difference with the new inventory count \(Y\) into \(total\): $\(total = total - A[X] + Y\)$
   • Update the inventory count of store \(X\) to \(Y\): $\(A[X] = Y\)$
   • Output the current \(total\).

This method allows each update and output to be performed in constant time.

Complexity

• Time complexity: \(O(N + Q)\)
  • The initial total calculation is \(O(N)\), and each query is processed in \(O(1)\), repeated \(Q\) times.
• Space complexity: \(O(N)\)
  • The size of the array \(A\) that stores the inventory count of each store.

Implementation Notes

• Since store numbers are given as 1-indexed in the input, convert them to 0-indexed internally (X -= 1).

• Pay attention to the order of the differential update: first update the total, then overwrite the value in the array.

  Source Code

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

# 入力の読み込み
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)

This editorial was generated by qwen3-coder-480b.