https://kanpurin.hatenablog.com/entry/2021/03/07/025421

問題概要

長さ ${N}$ の整数列 ${A}$ が与えられる． ${A}$ の連続する長さ ${M}$ の区間すべてについてのmexのうち最小値を求めよ．

${1\leq M\leq N\leq 1.5×10^6}$

最初の区間についてmexを求めた後，区間をずらしながらすべての区間についてのmexを求める．区間をずらすとき，変化するのは区間の端の数のみ．したがって区間中の整数の数は区間ごとに ${O(1)}$ でカウントできる．

mexは整数の集合により値が決まるのでsetうまく管理することで求めることができそう．

${\downarrow}$

現在の区間の整数の集合を ${S}$ とする． ${S}$ の連続する整数の端をsetで持つ．

例として ${S=\{1,2,3,4,6,8,9\}}$ とするとsetの中身は ${1,4,6,8,9}$ となる．

f:id:kanpurin:20210307023027p:plain

以下の図のように区間を隣り合った区間を接続する．隣に区間が無いなら追加した整数が区間の端になる．

f:id:kanpurin:20210307023955p:plain

以下の図のように区間を分割する．削除する整数が区間の端である場合も同様に行う．

f:id:kanpurin:20210307024346p:plain

${0}$ がない場合は ${0}$ が答え．

${0}$ がある場合は ${0}$ を含む区間の右端の整数 ${+1}$ が答え．

上の解法のほかにもっと簡単なものとしてsetに ${0}$ から ${N}$ までをつっこんで ${S}$ の整数をsetから削除する．このときset内の最小の整数が答えとなる．全部つっこむ分，上の解法より遅いが間に合う．

どちらも計算量は ${O(N\log{N})}$

公式解説ではmexとminの性質を用いて直接答えを求めていた．本解説の手法だと計算量は悪くなるがmexの列挙ができる．

問題文から素直な考え方で導かれる解法の解説を行った．実装は重くなるがいろいろ応用できそうな解法だと思う．