概要

各日の入出金 \(A_i\) のうち、指定された日を順に「無かったことにする（削除する）」とき、各操作後の最終残高（\(N\) 日目終了時点）を求める問題です。

考察

最終残高は、削除されていない取引の総和に等しいです。なぜなら、残高は初期値 \(0\) から始まり、各日 \(A_i\) を足し合わせた結果が \(N\) 日目終了時点の残高になるからです。

• 何も削除していないときの残高は \(S=\sum_{i=1}^{N} A_i\)
• ある日 \(d\) の取引を削除すると、その分だけ最終残高から \(A_d\) が取り除かれる
  よって新しい残高は \(S \leftarrow S - A_d\)

素朴な方法が遅い理由

各操作のたびに「削除済みを除いて合計を計算し直す」と、1 回の操作に \(O(N)\)、全体で \(O(NQ)\) になります。
制約は最大で \(N=2\times 10^5, Q=2\times 10^5\) なので、\(O(NQ)\) は現実的に間に合いません。

解決策

最初に合計 \(S=\sum A_i\) を 1 回だけ計算しておき、削除操作が来るたびに \(S\) から該当要素を引くだけにします。これなら各操作は \(O(1)\) です。

例えば \(A=[10, -3, 5]\) で初期合計 \(S=12\)。 - 2 日目（\(-3\)）を削除 → \(S=12-(-3)=15\) - 1 日目（\(10\)）を削除 → \(S=15-10=5\) のように更新できます。

アルゴリズム

1. 配列 \(A\) を読み込む。
2. \(total=\sum_{i=1}^{N} A_i\) を計算する。
3. 各クエリで削除日 \(D_j\) を受け取り、0-index に直して \(d=D_j-1\) とする。
4. \(total \leftarrow total - A[d]\) を行い、\(total\) を出力する。
   • 「同じ日の取引を複数回削除しない」ことが保証されているため、管理用のフラグ等は不要です（引き算を一度だけ行えばよい）。

計算量

• 時間計算量: \(O(N+Q)\)（最初の合計が \(O(N)\)、各操作が \(O(1)\) で \(Q\) 回）
• 空間計算量: \(O(N)\)（配列 \(A\) を保持）

実装のポイント

• 入力の \(D_j\) は \(1\) から始まるので、配列アクセス用に \(d=D_j-1\) として 0-index に直します。

• \(N,Q\) が大きいので、Python では sys.stdin.buffer.read() などの高速入力を使うと安全です。

• \(A_i\) は負になり得るため、削除時に total -= A[d] とすると、負の値の削除では合計が増える点に注意します（これは正しい挙動です）。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。