コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 2287 (記事作成時点)
供養
解法
- 各点 $u$ について、クエリ $i$ の時点での色が $x$ であったとする $C_{u} = (x, i)$ と、クエリ $i$ で隣接点に伝搬させた色が $x$ であったとする $X_{u} = (x, i)$ を持っておく
- クエリ $i$ において、点 $u = x_{i}$ がその時点で何色であったかを確定させるには、$C_{u}$ および $u$ の各隣接点 $v$ の $X_{v}$ のうち、もっとも新しい情報 i.e. 最大の $i$ を持つ $(x, i)$ を採用すればよい
- 比較対象とする $X_{v}$ を、$v$ の次数が一定数以上のものに限定する
- $v$ の次数が一定数以下であった場合、$v$ の評価時点で（$u$ を含む）$v$ の各隣接点 $w$ の $C_{w}$ を更新してしまい、改めて $u$ を評価する機会が訪れた場合に $X_{v}$ と比較させない
- $v$ の次数が一定以上の場合は $X_{v}$ だけ更新し、隣接点の $C_{w}$ は更新しない
- 次数の閾値を $B$ とすると、$u$ の周囲で比較対象となりうる点の数は高々 $\frac{2M}{B}$ であり、周囲の $C_{v}$ を更新する回数も高々 $B$
- $B = \sqrt{M}$ とすると、$C_{u}$ の更新も伝搬も $O(\sqrt{M})$ で実施できる
実装
計算量は $O(N + M + Q \sqrt{M})$
公式解説
躓いた点
