Overview

This is a problem where each time a store’s inventory is updated via a “point update (assignment),” we need to quickly update and output the total inventory across all stores.

Analysis

A naive approach of recalculating the total across all stores with each update (e.g., computing \(\sum A_i\) every time) costs \(O(N)\) per update. This results in an overall complexity of \(O(NQ)\), which for the maximum constraints of \(N,Q \le 2\times 10^5\) would be on the order of \(4\times 10^{10}\) operations, far too slow to finish in time (TLE).

The key insight is that “the total can be updated using only the difference.”

For example, when a store \(x\)’s inventory changes from \(A_x\) to \(y\), the overall total changes as follows: - The old value \(A_x\) is removed from the total - The new value \(y\) is added to the total

So the change in the total is \(y - A_x\). Therefore, by computing: - total += y - A[x]

we can update the total in \(O(1)\).

For this to work, we need to always maintain the current value \(A[x]\) for each store (so we can reference the “old value” during the next update).

Algorithm

1. Read the initial array \(A\) and compute the initial total \(total=\sum_{i=1}^N A_i\).
2. For each update \((X_j, Y_j)\):
   • Convert to 0-indexed: \(x = X_j - 1\).
   • Update the total using the difference: \(total \leftarrow total + (Y_j - A_x)\)
   • Update the array: \(A_x \leftarrow Y_j\)
   • Output \(total\).

(Example) - \(A=[3,1,4]\) with total \(total=8\) - Changing store 2 from \(1 \to 10\), the difference is \(10-1=9\) - The new total is \(8+9=17\)

Complexity

• Time complexity: \(O(N+Q)\) (\(O(N)\) for the initial total, \(O(1)\) per update)
• Space complexity: \(O(N)\) (to store the array \(A\))

Implementation Notes

• The store number \(X_j\) in the input is 1-indexed, so we need x -= 1 to match Python’s 0-indexed arrays.

• The total can be as large as \(N \times 10^9\), but since Python’s int has arbitrary precision, there is no concern about overflow (in other languages, use 64-bit integers).

• To speed up output, we accumulate each answer in a list and output them all at once at the end using "\n".join(...).

  Source Code

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

This editorial was generated by gpt-5.2-high.