AtCoder Beginner Contest 225 D 問題 Play Train

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 両の電車のおもちゃがあり, 前後を (高々1個) 連結できる. 以下の $Q$ 個のクエリを順に処理せよ.

Type 1: 電車 $x$ の後ろと電車 $y$ の前を連結させる.
Type 2: 電車 $x$ の後ろと電車 $y$ の前を分離する.
Type 3: 電車 $x$ が含まれる連結成分について, 電車の番号を前から出力する.

制約

$2 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$1, \leq x,y \leq N$
Type 1,2 において, 整合性を持つようにクエリが与えられる.
Type 3 において出力すべき整数は $Q$ 個のクエリを通して $10^6$ 個以下である.

解法

各電車について, その電車の直前 (直後) に電車は連結しているか? しているならば, それはどの電車か? という情報を記録すれば高速にクエリ処理できる. 実際には, ${\rm front}_i, {\rm back}_i$ で直前, 直後に連結している電車の番号 (存在しない場合は $0$ ) とすると,