Overview

This problem asks you to efficiently compute the total inventory across all stores each time a store’s inventory is updated.

Analysis

Naive Approach and Its Issues

The simplest method is to sum up the inventory of all stores after each update to calculate the total.

# Naive approach (will result in TLE)
for each_update:
    update_inventory
    total = sum(A)  # Takes O(N) each time
    print(total)

However, with this method: - Each sum calculation takes \(O(N)\) - With \(Q\) updates, the overall complexity is \(O(N \times Q)\) - Since \(N, Q\) can be up to \(2 \times 10^5\), this requires \(4 \times 10^{10}\) operations - This will not finish within the time limit (TLE)

Key Insight

Notice that each update only changes the inventory of one store.

For example, if store 3’s inventory changes from \(50\) to \(80\): - The total increases by \(80 - 50 = 30\) - Since other stores’ inventories don’t change, there’s no need to re-sum them every time

In other words, by updating only the difference, we can compute the new total in \(O(1)\).

Algorithm

1. Preprocessing: First, calculate the total inventory total across all stores
2. For each update:
   • Get the old inventory value of store \(X\) using A[X-1]
   • Update the total: total = total - (old value) + (new value)
   • Update the array: A[X-1] = new value
   • Output the updated total

Concrete Example

With \(N = 3\) and initial inventory \(A = [10, 20, 30]\):

• Initial total: \(total = 10 + 20 + 30 = 60\)

Update 1: Change store 2’s inventory to 50 - Old value: \(A[1] = 20\) - \(total = 60 - 20 + 50 = 90\) - \(A = [10, 50, 30]\) - Output: 90

Update 2: Change store 1’s inventory to 0 - Old value: \(A[0] = 10\) - \(total = 90 - 10 + 0 = 80\) - \(A = [0, 50, 30]\) - Output: 80

Complexity

• Time complexity: \(O(N + Q)\)
  • Initial sum calculation: \(O(N)\)
  • Each update operation: \(O(1)\) × \(Q\) times = \(O(Q)\)
• Space complexity: \(O(N)\)
  • Size of the array storing inventory

Implementation Notes

1. Converting between 1-indexed and 0-indexed

   • The problem uses store numbers starting from 1 (1-indexed)
   • Python arrays start from 0 (0-indexed)
   • Conversion is needed: idx = X - 1

2. Watch out for overflow

   • Each inventory can be up to \(10^9\), and there can be up to \(2 \times 10^5\) stores
   • The total can be as large as \(2 \times 10^{14}\)
   • Python handles arbitrary precision integers, so there’s no overflow issue (in C++, long long would be required)

3. Fast input

   • Using sys.stdin.readline allows for faster reading of large inputs

Source Code

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())
        # Store X is 1-indexed, so the array index is X-1
        idx = X - 1
        # Subtract the old value from total and add the new value
        total = total - A[idx] + Y
        # Update the inventory
        A[idx] = Y
        print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.