https://atcoder.jp/contests/abc134/submissions/10792162
二分探索の応用範囲が広すぎて困る。
分解数最小の増加部分列を作るという処理は、小さい積み木の上に大きい積み木を積み上げていくイメージになる。このとき、なるべく積み木の列が少なくなるようにする。そのためには高く積むために小さい数字を優先して残す。したがって、A[i]で二分探索して積むべき列を見つける処理をするのが最適解。積めないときは二分探索をデクリメントして新しい列になって欲しいので、予めサイズN+1だけ確保した-1とかLLONG_MINで初期化した配列を用意しておくと便利。
この処理は最長減少部分列(Longest Decreasing Subsequence)を得る処理と同値。最長減少部分列はインデックスの順番が昇順になるが、例えば図の「１」を一番上の積み木の列になるように移動させるとインデックスの順番が壊れる。したがって、{4,2,1}は最長減少部分列になる。
