AtCoder Beginner Contest 299 G - Minimum Permutation
メモ
Li(v) := vが現れるインデックスの内最も左
Ri(v) := vが現れるインデックスの内最も右
とする
辞書順最小なので、次の数にできる物の内最小のものを貪欲に決めていきたい。
値vを先頭にできるかの判定を考える。
l = Li(v)として[l+1, N)にv以外の値が全てあれば可能である
この問題は種類数を求めるクエリの下位互換だ
種類数のクエリについては以下の記事で触れられている
与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱
種類数を求めるには各要素の内、最も右にある場所のインデックスに1を入れたような配列について、区間の和を求めればいいことが分かる。
ある物が重複して数えられないように、それを数えるものを一つのものに対応させる際に、その決め方をgreedyにすると上手くいくというのは
greedyからの帰着に近いところがある...?
