CHT< T, MIN > 構造体テンプレート

Convex Hull Trick verify: https://judge.yosupo.jp/submission/291811 https://hcpc-hokudai.github.io/archive/algorithm_convex_hull_trick_001.pdf [詳解]

#include "cht.hpp"

公開メンバ関数
	CHT ()=default
void	add (T a, T b)
	直線 ax + b を追加する
T	get (T x)
	x に対する直線群の最小値を求める

詳解

template<typename T = ll, bool MIN = true>
struct CHT< T, MIN >

Convex Hull Trick verify: https://judge.yosupo.jp/submission/291811 https://hcpc-hokudai.github.io/archive/algorithm_convex_hull_trick_001.pdf

テンプレート引数

Min	true のとき最小値を管理する

cht.hpp の 9 行目に定義があります。

構築子と解体子

CHT()

template<typename T = ll, bool MIN = true>

CHT< T, MIN >::CHT ( )

default

関数詳解

add()

template<typename T = ll, bool MIN = true>

void CHT< T, MIN >::add ( T a, T b )

inline

直線 ax + b を追加する

覚え書き

O(log(N))

cht.hpp の 14 行目に定義があります。

get()

template<typename T = ll, bool MIN = true>

T CHT< T, MIN >::get ( T x )

inline

x に対する直線群の最小値を求める

覚え書き

O((log(N))^2)

cht.hpp の 44 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• algorithm/cht.hpp