UNICORNプログラミングコンテスト2021(ABC225) D - Play Train (400)
繋がっている電車を配列で持つと、結合や分解に$ \mathcal{O}(N)かかり、間に合わない
それぞれの電車に自分の前後の電車の番号と自身が先頭かの情報を持たせる
前後が存在しない場合、自身の番号を入れておく
クエリ1の場合
x,yの前後の電車情報を操作して繋げ、yの先頭フラグを折る
クエリ2の場合
x,yの前後の電車情報をそれぞれ自身にして、yの先頭フラグを立てる
クエリ3の場合
先頭フラグが立っているところまで前方向へ移動し、そこから次の先頭フラグの直前まで出力する
件数については先に1周回してカウントしておく
出力するクエリと同等の計算量で可能なので間に合う