Dynamic Convex Hull Trick
コードについての説明
Convex Hull Trickの傾きが単調でなくなった場合に対応する.
さらに動的に直線および線分の追加も可能である.
各直線が最小値を取る範囲を 動的セグ木
と同じ要領で必要な部分にのみノードを用意することで値の大きな範囲を管理することができる.
説明はたぶん色々とあると思う. 線分追加については高々 $\log$ 個のノードへの直線追加で行えるので $\log^2$ となる.
枝刈りを入れているのでひどいケースでない場合は見た目の計算量に比べてかなり高速に動作する.
(コンストラクタ)
CHT$(lpos, rpos)$ : 扱う $x$ 座標の範囲を $[lpos, rpos)$ とする
(関数)
add_line$(a, b)$ : 直線 $y=ax+b$ を追加する
add_segment$(a, b, c, d)$ : 線分 $y=ax+b\ (x \in [c, d))$ を追加する
query$(k)$ : $x=k$ での最小値を返す
時間計算量: add_line, query $\O (\log (rpos - lpos))$, add_segment $\O (\log^2 (rpos - lpos))$
コード(直線追加)
template<typename T> class CHT {
private:
struct node {
node *left, *right;
static const T inf = numeric_limits<T>::max();
T a, b;
node() : node(0, inf){}
node(const T _a, const T _b)
: left(nullptr), right(nullptr), a(_a), b(_b){}
T f(const T x) const { return a * x + b; }
};
static void swap(node *x, node *y){
std::swap(x->a, y->a), std::swap(x->b, y->b);
}
void _add_line(node *cur, node *nw, T l, T r){
while(true){
if(nw->f(l) < cur->f(l)) swap(cur, nw);
if(cur->f(r - 1) <= nw->f(r - 1)) break;
const T mid = (l + r) / 2;
if(cur->f(mid) <= nw->f(mid)){
if(!cur->right){
cur->right = new node(*nw);
break;
}else{
cur = cur->right, l = mid;
}
}else{
swap(cur, nw);
if(!cur->left){
cur->left = new node(*nw);
break;
}else{
cur = cur->left, r = mid;
}
}
}
}
T query(node *cur, const T k, T l, T r) const {
T ans = numeric_limits<T>::max();
while(cur){
ans = min(ans, cur->f(k));
const T mid = (l + r) / 2;
if(k < mid){
cur = cur->left, r = mid;
}else{
cur = cur->right, l = mid;
}
}
return ans;
}
void clear(node *cur){
if(cur->left) clear(cur->left);
if(cur->right) clear(cur->right);
delete cur;
}
const T lpos, rpos;
node *root;
public:
CHT(const T _lpos, const T _rpos) : lpos(_lpos), rpos(_rpos), root(new node()){
assert(lpos < rpos);
}
// ~CHT(){ clear(root); }
// f(x) = a * x + b を挿入
void add_line(const T a, const T b){
node nw(a, b);
return _add_line(root, &nw, lpos, rpos);
}
// x = k での最小値
T query(const T k) const {
return query(root, k, lpos, rpos);
}
};
コード(線分追加)
template<typename T> class CHT {
private:
struct node {
node *left, *right;
static const T inf = numeric_limits<T>::max();
T a, b, l, r;
node(const T _a, const T _b, const T _l, const T _r)
: left(nullptr), right(nullptr), a(_a), b(_b), l(_l), r(_r){}
T f(const T x) const {
return (l <= x && x < r) ? (a * x + b) : inf;
}
T tf(const T x) const {
return a * x + b;
}
bool isLine(const T _l, const T _r) const {
return (l == _l) && (r == _r);
}
};
static void swap(node *x, node *y){
std::swap(x->a, y->a), std::swap(x->b, y->b), std::swap(x->l, y->l), std::swap(x->r, y->r);
}
void _add_segment(node *cur, node *nw, T l, T r){
while(true){
const T mid = (l + r) / 2;
if(cur->f(nw->l) <= nw->tf(nw->l) && cur->f(nw->r - 1) <= nw->tf(nw->r - 1)){
break;
}
if(cur->tf(cur->l) >= nw->f(cur->l) && cur->tf(cur->r - 1) >= nw->f(cur->r - 1)){
swap(cur, nw);
break;
}
if(cur->isLine(l, r) && nw->isLine(l, r)){
if(nw->tf(l) < cur->tf(l)) swap(cur, nw);
if(cur->tf(mid) <= nw->tf(mid)){
if(!cur->right){
cur->right = new node(nw->a, nw->b, mid, r);
break;
}else{
cur = cur->right, l = mid, nw->l = mid;
}
}else{
swap(cur, nw);
if(!cur->left){
cur->left = new node(nw->a, nw->b, l, mid);
break;
}else{
cur = cur->left, r = mid, nw->r = mid;
}
}
continue;
}
if(nw->isLine(l, r)) swap(cur, nw);
if(nw->r <= mid){
if(!cur->left){
cur->left = new node(*nw);
break;
}else{
cur = cur->left, r = mid;
}
}else if(mid <= nw->l){
if(!cur->right){
cur->right = new node(*nw);
break;
}else{
cur = cur->right, l = mid;
}
}else{
node _nw(nw->a, nw->b, mid, nw->r);
nw->r = mid;
if(!cur->left){
cur->left = new node(*nw);
}else{
_add_segment(cur->left, nw, l, mid);
}
if(!cur->right){
cur->right = new node(_nw);
}else{
_add_segment(cur->right, &_nw, mid, r);
}
break;
}
}
}
T query(node *cur, const T k, T l, T r) const {
T ans = numeric_limits<T>::max();
while(cur){
ans = min(ans, cur->f(k));
const T mid = (l + r) / 2;
if(k < mid){
cur = cur->left, r = mid;
}else{
cur = cur->right, l = mid;
}
}
return ans;
}
void clear(node *cur){
if(cur->left) clear(cur->left);
if(cur->right) clear(cur->right);
delete cur;
}
const T lpos, rpos;
node *root;
public:
CHT(const T _lpos, const T _rpos)
: lpos(_lpos), rpos(_rpos),
root(new node(0, numeric_limits<T>::max(), lpos, rpos)){
assert(lpos < rpos);
}
// ~CHT(){ clear(root); }
// f(x) = a * x + b を挿入
void add_line(const T a, const T b){
node nw(a, b, lpos, rpos);
return _add_line(root, &nw, lpos, rpos);
}
// f(x) = a * x + b (x ∈ [l, r)) を挿入
void add_segment(const T a, const T b, const T l, const T r){
assert(l < r);
node nw(a, b, l, r);
return _add_segment(root, &nw, lpos, rpos);
}
// x = k での最小値
T query(const T k) const {
return query(root, k, lpos, rpos);
}
};
verify 用の問題
yosupo さんの library checker : Line Add Get Min
提出コード(直線追加の verify)
yosupo さんの library checker : Segment Add Get Min
提出コード(線分追加の verify)