ARC097 D - Equals

atcoder.jp

UnionFindの例題としてみたのでUnionFindを使うことは分かっていた状態だったけど解くことは出来なかった。。。 ので思いつく為に必要なことをまた考察してみる

• 場所iと値p_iを同一視する
• x,yのスワップをUnionFindに突っ込めば良さそうな雰囲気というところまで考えられたのにダメだったのはこの辺に理由がある気がする
• 順列を、1からN(の列)からp_1からp_Nへの写像であるという見方が効きそう
• 上記の延長でx,yのスワップも考えられる
• 交換しなくてもいいあみだくじなイメージ