Cartesian木
Cartesian Tree を実装しよう！ 具体的には、Yosupo Library Checker の問題「Cartesian Tree」を通すことにする。 問題概要 長さ の数列 (互いに異なる) から誘導される Cartesian Tree を求めて出力せよ。 具体的には Cartesian Tree の各頂点について、そ…
AtCoder
黄色diff
ABC-G
スライド最小値
Cartesian木
ある量を固定して考える
制約:数値が10^6以下
ヒストグラム内の極大長方形の列挙
stack
左右からそれぞれ走査する
二次元グリッド
最大スコア
制約条件:長方形領域
縦方向と横方向の情報を整理する
前処理
絶対値やminを扱う問題
極大なものを考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
区間
最大値や最小値に着目する
ヒストグラム
AtCoder575点
操作をstackを用いて高速化する
最適化問題
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
AtCoder
AtCoder600点
ABC-Ex
銅色diff
SuffixArray
DFS
再帰的に上位桁から順に値で分類した木を作る
再帰的構造に着目する
文字列
制約:複数系列の長さの合計が10^5以下
クエリ処理問題
queue
応用的な探索
lcp
Cartesian木
Suffix木
セグメント木
解空間:O(N^2)通りの選択肢
連続部分列を扱う問題
prefixとsuffix
辞書順
K番目を求める
非自明な線形時間
N個の文字列の問題
Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった！ 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…
