某に載せるほどか...? 載せることにしたらこっちは消えます 以下の操作を実現する永続データ構造が存在する 単一の要素 からなる列を作成する 時間/空間計算量 列 を連結した列を作成する 時間/空間計算量 列 の全要素を順に列挙する 時間計算量 アルゴリズ…

変数 への の割り当てに対してコストが以下の図のようになるとします。 コストを最小化するとき、 ならば最小カットで表現できます。 説明 最小カットで使えるプリミティブな操作を考えます また、解に直接値を加えることで全体に することが出来ます。 量 …

概要 Li Chao Tree で小さいほうから 個取得できる ただし取り出した 個の順番は保証されない 空間計算量 時間計算量 per query アルゴリズム 全てのノードは高々 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエ…

出来ない分割の例 木に対して、頂点集合を に分割する がつながっている: 内の任意の頂点対のパスは に含まれる が小さい: が小さい: 反例: スターグラフ 出来る分割の例 根付き木に対して、頂点集合を に分割する がつながっている: 内の任意の頂点対のパス…