概要

各操作は「ある作業台の部品を全部まとめて右隣へ移す（または最後なら捨てる）」だけなので、操作を順にそのままシミュレーションして最終状態を求めます。

考察

重要な観察は次の2点です。

• スイッチを押した作業台 \(i\) の変化は、作業台 \(i\) と（\(i<N\) なら）作業台 \(i+1\) にしか影響しません。
  つまり、1回の操作は 局所的（定数個の要素の更新） です。
• 部品は「1個ずつ流れる」のではなく「その作業台にある分が全部一括で移動」します。
  よって、毎回「移動する個数 \(x\) を取り出して隣に足し、元を0にする」だけで済みます。

素朴に「部品を1個ずつ動かす」ような実装をすると、部品数が最大で \(2\times 10^{14}\) にもなり得るため、操作1回で莫大な回数の更新が必要になってTLEになります。しかし本問題の操作は一括移動なので、部品数に依存しない \(O(1)\) 更新で処理できます。

例：\(N=4,\ A=[3,0,2,1]\) で作業台2のスイッチを押しても、\(A_2=0\) なので何も起きません。
作業台1を押すと、\(3\) 個が作業台2へ移り \([0,3,2,1]\) になります（1個ずつ動かす必要はありません）。

アルゴリズム

配列 \(A\) を「各作業台の現在の部品数」として持ち、操作を入力順に処理します。

各操作で押す作業台を \(b\)（0-index）とすると：

• もし \(b = N-1\)（最後の作業台）なら
  
  • \(A[b] \leftarrow 0\)（ライン外に排出）
• それ以外なら
  
  • \(x \leftarrow A[b]\)
  • \(A[b] \leftarrow 0\)
  • \(A[b+1] \leftarrow A[b+1] + x\)

\(A[b]=0\) のときは \(x=0\) なので何も変わらず、問題文の仕様と一致します（コードでは軽い最適化として \(x\) が0なら加算を省略しています）。

計算量

• 時間計算量: \(O(N+Q)\)（初期配列の読み込みが \(O(N)\)、各操作が \(O(1)\)）
• 空間計算量: \(O(N)\)（配列 \(A\)）

実装のポイント

• \(N,Q \le 2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() による一括読み込みが安全です。

• 添字を 0-index に直すため、入力の \(B_j\) から \(1\) を引きます。

• 値は最大 \(2\times 10^{14}\) まで増え得ますが、Pythonの整数はオーバーフローしません。

  ソースコード

import sys

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

    for _ in range(Q):
        b = next(it) - 1
        if b == N - 1:
            A[b] = 0
        else:
            x = A[b]
            if x:
                A[b] = 0
                A[b + 1] += x

    sys.stdout.write(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

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