atcoder abc455_d

1. 問題

カード $1,\dots,N$ と山 $1,\dots,N$ があり、初期状態では山 $i$ にカード $i$ だけが積まれています。

$Q$ 回の操作で、カード $C_i$ とその上にあるカードすべてを、順序を保ったままカード $P_i$ の上へ移動します。

各操作の直前には、$C_i$ と $P_i$ は異なる山にあり、$P_i$ はその山の一番上にあることが保証されています。

すべての操作後、各山 $i$ に残っているカード枚数 $A_i$ を求め、$A_1,A_2,\dots,A_N$ を空白区切りで出力します。

制約は $1 \leq N,Q \leq 3 \times 10^5$ です。

D – Card Pile Query

2. 素朴な回

3. 途中はあれこれあっても最後に何の上にあるかだけ