問題はこちら
問題概要
長さの整数列が与えられる.の連続する長さの区間すべてについてのmexのうち最小値を求めよ.解説
最初の区間についてmexを求めた後,区間をずらしながらすべての区間についてのmexを求める.区間をずらすとき,変化するのは区間の端の数のみ.したがって区間中の整数の数は区間ごとにでカウントできる.
mexは整数の集合により値が決まるのでsetうまく管理することで求めることができそう.
現在の区間の整数の集合をとする.の連続する整数の端をsetで持つ.
例としてとするとsetの中身はとなる.
に整数を追加する場合
以下の図のように区間を隣り合った区間を接続する.隣に区間が無いなら追加した整数が区間の端になる.から整数を削除する場合
以下の図のように区間を分割する.削除する整数が区間の端である場合も同様に行う.のmexを求める
がない場合はが答え.がある場合はを含む区間の右端の整数が答え.
ほかにも
上の解法のほかにもっと簡単なものとしてsetにからまでをつっこんでの整数をsetから削除する.このときset内の最小の整数が答えとなる.全部つっこむ分,上の解法より遅いが間に合う.どちらも計算量は
公式解説ではmexとminの性質を用いて直接答えを求めていた.本解説の手法だと計算量は悪くなるがmexの列挙ができる.
提出プログラム
https://atcoder.jp/contests/abc194/submissions/20738573https://atcoder.jp/contests/abc194/submissions/20740038