トヨタシステムズプログラミングコンテスト2022 (AtCoder Beginner Contest 279) F - BOX (500)
自分の解法
ボール毎に自分が実際に何番目の箱にいるかを持つ
箱毎に入れ替えた先の箱、今付いているラベル、最初につけたラベルを持つ
入替先は最初は自分自身
今付いているラベルは最初につけたラベルと同じ値だが操作1をすると無効化
最初につけたラベルは箱を作ったタイミングで付く
最初の$ N個は自分自身の値
最初の$ N箱分について実際には何番目の箱がその箱の扱いになっているかを持っておく
それぞれのクエリで以下を行う
操作1
箱x,yそれぞれについて実際に箱に今付いているラベルが無効ならその箱に対応する実際の箱を新しく作る
2種類のラベルは今作りたい箱の番号
実際の箱の対応付けをこの箱に更新
入れ替えた先を自身に設定
yを担当する実際の箱の入れ替え先をxを担当する実際の箱に変更
yを担当する実際の箱の今のラベルを無効化
操作2
箱xについて実際に箱に今付いているラベルが無効ならその箱に対応する実際の箱を新しく作る
新しいボールをxを担当する実際の箱に入れる
操作3
ボールが入っている箱の親を辿れなくなるまで辿っていく
ここで経路圧縮もしておく
その箱に最初につけたラベルが答え
操作1,2は$ \mathcal{O}(1)で可能で操作3も経路圧縮することで全体で$ \mathcal{O}(Q)なので全体で$ \mathcal{O}(N+Q)
解説の解法
UnionFindを使うと管理するべき情報が減る
集合毎の代表元ldと代表元毎にどの箱に入っているかを管理するだけ
操作1
箱yが空なら何もしない
箱xが空ならy->xに移動させるような変更を行う
そうでないなら箱x,yの集合をマージして新しい代表元とxを紐付ける
箱yの代表元だった方は対応を消しておく
操作2
箱xが空なら今追加したのが自動的に代表元に
そうでないなら箱xの集合とマージして新しい代表元とxを紐付ける
操作3
xの所属する集合の代表元の箱を返す