drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ YosupoLibraryChecker Cartesian木 データ構造 stack 入れ子構造 非自明な線形時間 テーマ解説記事 操作をstackを用いて高速化する Cartesian Tree を実装しよう！ 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、その親頂点の番号を出力せよ (根については自分自身を親とする)。 ただし、数列中の最も小さい要素を根とすることにする。 制約 Cartesian Tree とは 数列から誘導される Cartesian Tree とは、下図のような二分木だ (wikipedia より)。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F10%2F19%2F025800" title="Cartesian Tree の実装 〜 stack を用いた O(N) 時間構築 - けんちょんの競プロ精進記録" 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/d/drken1215/20231019/20231019025137.png Hatena Blog https://hatena.blog 2023-10-19 02:58:00 rich https://drken1215.hatenablog.com/entry/2023/10/19/025800 1.0 100%