Overview

Given daily deposits/withdrawals \(A_i\), when specified days are sequentially “undone (deleted)” one by one, find the final balance (at the end of day \(N\)) after each operation.

Analysis

The final balance equals the sum of all non-deleted transactions. This is because the balance starts at an initial value of \(0\), and the balance at the end of day \(N\) is the result of adding up each day’s \(A_i\).

• The balance with nothing deleted is \(S=\sum_{i=1}^{N} A_i\)
• When the transaction on day \(d\) is deleted, \(A_d\) is removed from the final balance.
  Therefore, the new balance is \(S \leftarrow S - A_d\)

Why a naive approach is too slow

If we “recompute the total excluding deleted entries” for each operation, a single operation takes \(O(N)\), and the overall complexity becomes \(O(NQ)\).
The constraints are up to \(N=2\times 10^5, Q=2\times 10^5\), so \(O(NQ)\) is not feasible in practice.

Solution

Compute the total \(S=\sum A_i\) just once at the beginning, and for each deletion operation, simply subtract the corresponding element from \(S\). This way, each operation is \(O(1)\).

For example, with \(A=[10, -3, 5]\) and initial total \(S=12\): - Delete day 2 (\(-3\)) → \(S=12-(-3)=15\) - Delete day 1 (\(10\)) → \(S=15-10=5\)

The updates can be performed like this.

Algorithm

1. Read the array \(A\).
2. Compute \(total=\sum_{i=1}^{N} A_i\).
3. For each query, receive the day to delete \(D_j\), and convert to 0-indexed: \(d=D_j-1\).
4. Perform \(total \leftarrow total - A[d]\) and output \(total\).
   • Since it is guaranteed that “the same day’s transaction is never deleted more than once,” there is no need for management flags or similar mechanisms (subtraction only needs to be done once).

Complexity

• Time complexity: \(O(N+Q)\) (the initial sum is \(O(N)\), and each operation is \(O(1)\) for \(Q\) operations)
• Space complexity: \(O(N)\) (to store the array \(A\))

Implementation Notes

• Since the input \(D_j\) is 1-indexed, convert to 0-indexed for array access: \(d=D_j-1\).

• Since \(N,Q\) can be large, in Python it is safer to use fast input methods such as sys.stdin.buffer.read().

• Since \(A_i\) can be negative, note that when deleting with total -= A[d], deleting a negative value will increase the total (this is the correct behavior).

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    Q = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    total = sum(A)

    out_lines = []
    for _ in range(Q):
        d = int(next(it)) - 1
        total -= A[d]
        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.