問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 個の箱 $1,2, \dots, N$ と $10^{100}$ 個のボール $1,2, \dots, 10^{100}$ がある. 最初, 箱 $i$ にはボール $i$ のみが入っている.

次の $Q$ 個のクエリを順に処理せよ.

Type 1 : 箱 $Y$ に入っているボールを全て箱 $X$ に移す.
Type 2 : この時点で $N$ 個の箱に入っているボールの数を $k$ としたとき, ボール $(k+1)$ を箱 $X$ に入れる.
Type 3 : ボール $X$ が入っている箱の番号を答える.

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq Q \leq 3 \times 10^5$
Type 1 : $1 \leq X,Y \leq N, X \neq Y$
Type 2 : $1 \leq X \leq N$
Type 3 : そのクエリが与えられた時点でボール $X$ がいずれかの箱に入っている.
Type 3 のクエリが1個以上存在する.

解法

まず, 最初に $N$ 個のボールがあって, 途中で加えられるボールの数は高々 $(Q-1)$ 個 *1 であるから, 高々 $(N+Q)$ 番までのボールについてを考えれば良い.

そして, このクエリにおいて, 相異なる2つのボールが同じ入っている瞬間があった場合, それ以降は常にその2つの箱は同じ箱に入っていることに気づく.

よって, Union Find による Union が有効になる. Union Find は無向グラフにおける連結成分に対する操作ともみなせるから, 次のように問題を帰着できる.

$(N+Q)$ 頂点 $0$ 辺の無向グラフ $G$ がある. なお, 頂点は $1,2, \dots, N+Q$ と名付けられている. また, 最初, 頂点 $i~(1 \leq i \leq N)$ は色 $i$ で塗られていて, 頂点 $i~(N \lt i \leq N+Q)$ は色 $0$ で塗られている. 次の $Q$ 個のクエリを順に処理せよ.

Type 1 : 色が $X$ であるような頂点と色が $Y$ であるような頂点同士を全て無向辺で結び, 色が $Y$ であるような頂点を全て頂点 $X$ で塗替える.
Type 2 : 色が $0$ であるような頂点のうち, 番号が最小であるものを $Z$ とする. 頂点 $Z$ を色 $X$ で塗る.
Type 3 : 頂点 $X$ の色を答えよ.

クエリの高速化を目指す.

同じ連結成分にある頂点は全て同じ色なので, 各頂点に色を持たせるのではなく, 各連結成分に色をもたせれば良い.
Type 2 において, 既に色が $X$ であるような頂点が存在するならば, そのような頂点たちと頂点 $Z$ を結ぶ辺を追加することにする. このことにより, 各色に対して, その色で塗られている連結成分の数が常に1個以下になる.
Type 1 において, 上で述べたことから, 色が $X$ であるような頂点と色が $Y$ であるような頂点同士を全て無向辺で結ぶのではなく, (両者をみたすような頂点が存在する場合) 色が $X$ であるような頂点1個と色が $Y$ であるような頂点1個を選び出し, それらを結ぶだけで十分である.
Type 2 はタイプ $1$ に於ける $(X,Y)=(X,Z)$ と考えることが出来る.

以上から, 次のようにして高速に処理できる.

$(N+Q)$ 頂点の Union Find $U$ を用意する.
$R_i=i$ であるような列 $R$ を用意する. この列は色が $i$ であるような頂点を1つ見つける際に用いられる (存在しない場合は $R_i=-1$ とする)
クエリの順に次を実行する.
- Type 1 : 色がであるような頂点が存在しない (つまり, ) 場合は何もしない. 以降は存在する場合とする.
  - 色が $X$ であるような頂点が存在しない場合, $R_Y$ が属する連結成分の色を $X$ にする. その後, $R_X \gets R_Y, R_Y \gets -1$ とする.
  - 色が $X$ であるような頂点が存在する場合, $U$ において, $R_Y$ を $R_X$ に merge させる. その後, $R_Y \gets -1$ とする.
- Type 2 : (Type 1 に帰着させる)
- Type 3 : 頂点 $X$ が属しているような連結成分の色を答える.