Overview

This is a problem where we need to find the final balance after sequentially deleting transactions on specified dates from Takahashi’s household account book.

Key Insight

The important observation in this problem is that instead of recalculating the sum of all transactions each time, we can simply subtract the deleted transactions from the initial total.

For example, if we precompute the sum of all transactions, the operation of deleting transaction \(A_d\) on day \(d\) can be done by simply subtracting that amount from the total. This eliminates the need to scan all \(N\) elements each time, allowing for efficient processing.

Additionally, since there is a constraint that the same day will not be deleted twice, we need to manage flags to ensure that already-deleted days are not processed again.

The key idea is: precompute the overall total and then update it by only applying the differences.

Algorithm

1. First, compute the total sum of all transactions total: $\( \text{total} = \sum_{i=1}^{N} A_i \)$

2. Process each operation as follows:

   • If the transaction \(A[D_j - 1]\) corresponding to the day \(D_j\) to be deleted has not been deleted yet:
     • Subtract that amount from total
     • Set the deleted flag
   • Append the current total to the result list

This method allows each query to be processed in constant time.

Complexity

• Time complexity: \(O(N + Q)\)
  • Initial sum computation is \(O(N)\), and each query is processed in \(O(1)\) × \(Q\) times
• Space complexity: \(O(N)\)
  • Due to the input array and the array for deletion flags

Implementation Notes

• Since indices are 0-based, day \(D_j\) needs to be handled as \(D_j - 1\).

• Use a boolean array to manage deletion status and prevent deleting the same day multiple times.

• For cases where fast input is needed, consider using sys.stdin.read or similar methods.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    A = list(map(int, data[2:2+N]))
    D = list(map(int, data[2+N:2+N+Q]))
    
    # 初期の合計を計算
    total = sum(A)
    
    # 削除されたかどうかを管理する配列
    removed = [False] * N
    
    results = []
    for d in D:
        idx = d - 1  # 0-indexedにする
        if not removed[idx]:
            total -= A[idx]
            removed[idx] = True
        results.append(total)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

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