問題はこちら
問題概要
解説
辞書順最小と言えば，前から貪欲に置けるもののうち最も小さいものを順に並べていく方法が考えられます．今回の問題もその方針で考えていきます．以下のサンプルを例に説明していきます．
出来るだけ小さい数字を先頭に選びたいため，まずは答えとなる部分列の先頭の数字がであるかどうかを考えてみます．
すると，以下の図の色付きの数列から答えとなる部分列を選択する必要が出てきますが，が色付きの部分に含まれていないため
を部分列の先頭として選ぶことはできません．
このように，それを部分列の先頭として選ぶと，条件を満たす部分列を選ぶことができなくなるようなものは選べません．したがって，それを部分列の先頭として選んでも条件を満たす部分列を選ぶことができなくならないようなものの中でもっとも値が小さいものを貪欲に選べば良いです．
ここで，から
の整数それぞれに対して一番後ろに出現するものに色を付けます．
先程の考察から，から
までの中から答えの部分列の先頭要素を選ぶことになります(そうでなければ部分列がすべての数を含むことができない)．
ここでは，最小要素のを選び，以降の
を選ぶことができなくします．
次の要素は，先程選んだ要素(青)の直後の要素から「まだ選んでない数それぞれに対して一番後ろに出現するもの(橙)」のうち一番先頭にある要素までの中から選びます．
これを繰り返していくことで辞書順最小の部分列を作ることができます．
必要な操作は
- 「まだ選んでない数それぞれに対して一番後ろに出現するもの」のうち一番先頭にある要素を求める
- 区間内のまだ使用していない値のうち最小要素を求める
- 選んだ要素と同じ値をもつ要素を使用不可にする
です．最初の操作はstd::setを用いれば可能，2番目の操作はSegment Treeを用いれば可能，最後の操作はSegment Treeで使用した要素をとすればよいです．
