miscalc https://blog.hatena.ne.jp/miscalc/ miscalc のブログ https://miscalc.hatenablog.com/ 概要 数列の各要素について「LIS に使われる可能性があるか、使われる場合 LIS の何番目か」を計算しておくといろいろ便利です。 前提 増加部分列は「値」というよりは「添字」をとってきたものと思うのが見通しがよいです。この記事では次のように、増加部分列を添字の列として定義します： 長さ の数列 の増加部分列とは、添字の列 であって、 かつ を満たすもの。最長増加部分列 (LIS) とは、増加部分列のうち、長さ が最大のもの。 また、LIS 長を求める 種類の DP（二分探索、セグ木）は既知として進めます。 本題 まず、添字 が LIS に使われる場合、その LIS 上での位置は一意です（そう… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmiscalc.hatenablog.com%2Fentry%2F2024%2F07%2F25%2F212618" title="LIS になる列の構造 - miscalc のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/m/miscalc/20240725/20240725154630.png Hatena Blog https://hatena.blog 2024-07-25 21:26:18 rich https://miscalc.hatenablog.com/entry/2024/07/25/212618 1.0 100%