Overview

This problem asks you to sequentially remove transactions from specified days from the total of \(N\) days of transaction records, and find the account balance after each removal.

Analysis

Key Insight

The key point is that the account balance equals the sum of all transactions.

For example, if \(A = [100, -50, 200]\): - End of day 1: \(100\) yen - End of day 2: \(100 + (-50) = 50\) yen - End of day 3: \(100 + (-50) + 200 = 250\) yen

The final balance is simply the sum \(A_1 + A_2 + \cdots + A_N\).

Problem with the Naive Approach

If we use an approach of “summing all transactions from non-deleted days” for each query, it requires \(O(N)\) computation per query. With \(Q\) queries, this becomes \(O(NQ)\) overall, which risks TLE (Time Limit Exceeded) when \(N, Q\) can be up to \(2 \times 10^5\).

Solution

We use incremental updates.

• First, calculate the total sum of all transactions in total
• Each time a transaction is deleted, simply subtract that transaction amount from total to get the new balance

This allows us to process each query in \(O(1)\).

Algorithm

1. Preprocessing: Calculate the sum of array \(A\) and store it in variable total
2. Processing each query:
   • Read the day \(D\) to be deleted
   • Subtract \(A_{D}\) (the transaction amount on day \(D\)) from total
   • Output the updated total

Concrete Example

For \(N = 4, Q = 2\), \(A = [100, -30, 50, -20]\):

• Initial total = \(100 + (-30) + 50 + (-20) = 100\)

Query 1: \(D = 2\) (delete day 2) - total = \(100 - (-30) = 130\) - Output: 130

Query 2: \(D = 4\) (delete day 4) - total = \(130 - (-20) = 150\) - Output: 150

Complexity

• Time complexity: \(O(N + Q)\)
  • \(O(N)\) for the initial sum calculation
  • \(O(1)\) × \(Q\) times = \(O(Q)\) for processing each query
• Space complexity: \(O(N)\)
  • For storing array \(A\)

Implementation Notes

• 1-indexed to 0-indexed conversion: In the problem statement, days start from 1 (1-indexed), but Python lists start from 0 (0-indexed), so the transaction on day \(D\) is accessed with A[D - 1].
• Integer range: \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), so the sum can be up to approximately \(2 \times 10^{14}\). In Python, you don’t need to worry about integer overflow, but in other languages, you need to use types like long long.

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate initial total
    total = sum(A)
    
    # Process each query
    for _ in range(Q):
        D = int(input())
        # Delete transaction on day D (D-1 since 1-indexed)
        total -= A[D - 1]
        print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.