ConvexHullTrick
(src/data_structure/convex_hull_trick.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/convex_hull_trick.hpp"

ConvexHullTrick

• 直線 $y = ax + b$ の追加
• 与えられた $x$ 座標における直線群の $y$ 座標の最小値の取得

をならし $O(1)$ で処理するデータ構造です．

ただし，追加される直線の $a$ は単調非増加である必要があります．
また，最小値クエリの $x$ は単調非減少である必要があります．

コンストラクタ

ConvecHullTrick<T> cht

空の直線群 cht を構築します．

計算量

• $O(1)$

add

void cht.add(T a, T b)

cht に直線 $y = ax + b$ を追加します．

制約

• $a$ は単調非増加

計算量

• 償却 $O(1)$

operator ()

T cht(T x)

与えられた $x$ 座標における，直線群 cht の $y$ 座標の最小値を取得します．

制約

• $x$ は単調非減少

計算量

• 償却 $O(1)$

Depends on

• template (src/template/template.hpp)

Code

#pragma once
#include "../template/template.hpp"
template <typename T>
struct ConvexHullTrick {
    void add(const T& a, const T& b) {
        Linear l(a, b);
        assert(ls.empty() or ls.back().a >= l.a);
        int len = (int)ls.size();
        while(len >= 2 and check(ls[len - 2], ls[len - 1], l)) {
            --len;
            ls.pop_back();
        }
        ls.emplace_back(l);
    }
    T operator()(const T& x) {
        assert(x >= x_last);
        while((int)ls.size() >= 2 and ls[0](x) >= ls[1](x)) {
            ls.pop_front();
        }
        x_last = x;
        return ls[0](x);
    }

   private:
    struct Linear {
        T a, b;
        Linear(const T& a = 0, const T& b = 0)
            : a(a), b(b) {}
        inline T operator()(const T& x) const {
            return a * x + b;
        }
    };
    inline bool check(const Linear& f1, const Linear& f2, const Linear& f3) const {
        return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a);
    }
    deque<Linear> ls;
    T x_last = numeric_limits<T>::min();
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/convex_hull_trick.hpp"
template <typename T>
struct ConvexHullTrick {
    void add(const T& a, const T& b) {
        Linear l(a, b);
        assert(ls.empty() or ls.back().a >= l.a);
        int len = (int)ls.size();
        while(len >= 2 and check(ls[len - 2], ls[len - 1], l)) {
            --len;
            ls.pop_back();
        }
        ls.emplace_back(l);
    }
    T operator()(const T& x) {
        assert(x >= x_last);
        while((int)ls.size() >= 2 and ls[0](x) >= ls[1](x)) {
            ls.pop_front();
        }
        x_last = x;
        return ls[0](x);
    }

   private:
    struct Linear {
        T a, b;
        Linear(const T& a = 0, const T& b = 0)
            : a(a), b(b) {}
        inline T operator()(const T& x) const {
            return a * x + b;
        }
    };
    inline bool check(const Linear& f1, const Linear& f2, const Linear& f3) const {
        return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a);
    }
    deque<Linear> ls;
    T x_last = numeric_limits<T>::min();
};

Back to top page