概要

\(N\) 段の植木鉢があり、それぞれに水が入っています。ある操作を \(Q\) 回行い、各操作で指定された植木鉢の水が一部蒸発し、残りが次の段へ流れていきます。すべての操作後、各植木鉢に残る水の量を求めます。

考察

この問題では、植木鉢に溜まっている水に対して「蒸発」と「流れ下り」の処理を行います。特に重要なのは、水は上から下へと一方向にしか流れず、戻らないという点です。つまり一度下の段に流れてしまった水は、それ以上上の段に戻ることはありません。

素朴なアプローチの問題点

素朴には、毎回指定された植木鉢の水を処理して、残りを次の段に加算すれば良さそうです。しかし、これだと最悪ケースで各操作ごとに多くの水が移動することになり、時間計算量が \(O(N \cdot Q)\) となり、制約が \(N, Q \leq 2 \times 10^5\) なので間に合いません（最大で \(4 \times 10^{10}\) 回の計算が必要になる）。

改善方法

しかしよく考えると、ある植木鉢の水は操作によって一度処理されると、以後その場所には残らず下に流れてしまうため、過去の操作履歴を全部覚えておく必要はありません。つまり、各操作において直接的にその場の水を減らして、次の植木鉢に足すだけで良いのです。

このような「過去の影響を気にせず、今現在の状態だけを見て処理できる」性質があるため、シミュレーションで解くことができます。

アルゴリズム

1. 初期状態として、各植木鉢の水の量を配列 water に格納します。
2. 各操作について以下のように処理します：
   • 操作対象の植木鉢 \(c\) のインデックス \(idx = c - 1\) を取得
   • その植木鉢の現在の水量を current、蒸発量を evap とする
   • 蒸発する水の量：\(\min(\text{current}, \text{evap})\)
   • 流れ落ちる水の量：\(\text{current} - \min(\text{current}, \text{evap})\)
   • その植木鉢の水量を 0 にし、流れ落ちた水を次の段（\(idx + 1\)）に加える（ただし \(N\) 段目なら排水されるので何もしない）
3. すべての操作が終わったら、最終的な water 配列を出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  各操作が定数時間で処理でき、初期化も線形時間なので全体で \(O(N + Q)\)。
• 空間計算量: \(O(N)\)
  植木鉢の水の量を管理する配列のみを使用。

実装のポイント

• インデックスの変換（1-origin から 0-origin へ）に注意
• 最後の植木鉢（\(N\) 番目）からは水が流れ落ちて排水されるので、範囲外アクセスにならないよう条件分岐を入れる
• 入力を高速に読み込むために sys.stdin.read を使用している（Python の標準入力が遅いため）

## ソースコード

```python
import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    
    A = list(map(int, data[2:2+N]))
    B = list(map(int, data[2+N:2+2*N]))
    C = list(map(int, data[2+2*N:2+2*N+Q]))
    
    # 水の量を管理する配列
    water = A[:]
    
    # 各植木鉢について、何回日光を浴びたかを記録する
    # ただし直接シミュレーションすると遅いので、差分更新的な考え方をする
    
    # 各操作で指定された植木鉢に対して処理を行う
    for c in C:
        idx = c - 1
        current = water[idx]
        evap = B[idx]
        # 蒸発する量
        lost = min(current, evap)
        # 下に流れる量
        flow = current - lost
        # 自分の水をゼロにする
        water[idx] = 0
        # 下の植木鉢に流れる（ただし最後の段なら排水される）
        if idx + 1 < N:
            water[idx + 1] += flow
            
    print(' '.join(map(str, water)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。