Convex Hull Trick (Add-Monotonic Slope Optimization)
(src/datastructure/ConvexHullTrick.hpp)

• View this file on GitHub
• Last update: 2024-06-04 01:15:26+09:00
• Include: #include "src/datastructure/ConvexHullTrick.hpp"

概要

直線 $f(x) = ax + b$ の追加（ただし, $a$ は単調増加もしくは単調減少）及びある $x$ での最小値（最大値）クエリを効率的に処理するデータ構造． 最小値を求めることを考えると，

• 固定された $x$ に対して最小値を取る直線の傾きは $x$ が増加するにつれて減少する．
• 不必要な直線がない（どの直線もそれで最小値を取るような $x$ が存在する）とき，固定された $x$ での直線上の値は直線の傾き順に並べると下に凸となる．

といった性質があることに注目して高速化が行える． 1 つ目の性質より，直線は傾きの降順に追加される deque によって管理することが可能である． 2 つ目の性質より最小値クエリは二分探索によって答えることができる． また，最小値クエリにおける $x$ にも単調性がある際にはさらに計算量を削減することができる．

以下に記す時間計算量における $n$ は追加される直線の本数，$q$ は最小値クエリの数である．

メンバ関数	効果	時間計算量
empty()	直線が空か確認する．	$O(1)$
add(a, b)	直線 $f(x) = ax + b$ を追加する．	全体 $O(n)$
query(x)	$x$ における最小値を求める．	クエリ $O(\log n)$
query_monotone_inc(x)	$x$ が単調増加であるときに最小値を求める．	全体 $O(n + q)$
query_monotone_dec(x)	$x$ が単調減少であるときに最小値を求める．	全体 $O(n + q)$

問題例

• Codeforces Round #222 (Div. 1) E. Cookie Clicker
• Codeforces Round #549 (Div. 1) C. U2
• AtCoder Regular Contest 051 D - 長方形
• COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) M. Managing Telephone Poles
  • 式変形すると， \(\begin{aligned} (x_i - x_j)^2 + (y_i - y_j)^2 &= (-2x_ix_j - 2y_iy_j + x_j^2 + y_j^2) + (x_i^2 + y_i^2) \\ &= \left[-2x_jx_i + \left(-2\frac{y_j}{x_j}y_i + x_j + \frac{y_j^2}{x_j}\right)x_j\right] + (x_i^2 + y_i^2) \\ \end{aligned}\) となる． カッコ内の式は内側から順に計算していけばそれぞれ $y_i, x_i$ の $1$ 次式の最小化と見なせる． クエリや直線追加の順番を適切にすることで全体 $O(nm)$ で解くことができる．

Links

• Convex-Hull Trick - sataniC++
• Convex-Hull-Trick-Add-Monotone | Luzhiled’s Library

Verified with

• test/yukicoder/952.test.cpp

Code

#pragma once
#include <cassert>
#include <queue>

template <typename T, bool isMin = true> struct ConvexHullTrick {
    std::deque<std::pair<T, T>> lines;  // slope decreases as index increases

    bool empty() const { return lines.empty(); }

    void add(T a, T b) {
        if (!isMin) a *= -1, b *= -1;
        std::pair<T, T> l(a, b);
        if (empty()) {
            lines.emplace_back(a, b);
            return;
        }
        if (lines.front().first <= a) {
            if (lines.front().first == a) {
                if (lines.front().second <= b) return;
                lines.pop_front();
            }
            while (lines.size() >= 2 && check(l, lines.front(), lines[1])) lines.pop_front();
            lines.emplace_front(l);
        } else if (a <= lines.back().first) {
            if (lines.back().first == a) {
                if (lines.back().second <= b) return;
                lines.pop_back();
            }
            while (lines.size() >= 2 && check(lines[lines.size() - 2], lines.back(), l)) lines.pop_back();
            lines.emplace_back(l);
        } else
            assert(false);
    }

    T query(T x) {
        assert(!called_query_monotonic_inc && !called_query_monotonic_dec);
        assert(!empty());
        called_query = true;
        int lb = -1, ub = lines.size() - 1;
        while (ub - lb > 1) {
            int mid = (ub + lb) >> 1;
            (f(lines[mid], x) >= f(lines[mid + 1], x) ? lb : ub) = mid;
        }
        T res = f(lines[ub], x);
        return isMin ? res : -res;
    }

    T query_monotone_inc(T x) {
        assert(!called_query && !called_query_monotonic_dec);
        assert(!empty());
        if (!called_query_monotonic_inc)
            called_query_monotonic_inc = true;
        else
            assert(prev_query <= x);
        prev_query = x;
        while (lines.size() >= 2 && f(lines.front(), x) >= f(lines[1], x)) lines.pop_front();
        T res = f(lines.front(), x);
        return isMin ? res : -res;
    }

    T query_monotone_dec(T x) {
        assert(!called_query && !called_query_monotonic_inc);
        assert(!empty());
        if (!called_query_monotonic_dec)
            called_query_monotonic_dec = true;
        else
            assert(x <= prev_query);
        prev_query = x;
        while (lines.size() >= 2 && f(lines.back(), x) >= f(lines[lines.size() - 2], x)) lines.pop_back();
        T res = f(lines.back(), x);
        return isMin ? res : -res;
    }

  private:
    bool called_query = false, called_query_monotonic_inc = false, called_query_monotonic_dec = false;
    T prev_query;

    using D = long double;

    // check if b is unnecessary
    inline bool check(const std::pair<T, T>& a, const std::pair<T, T>& b, const std::pair<T, T>& c) {
        // return (b.first - a.first) * (c.second - b.second) >= (c.first - b.first) * (b.second - a.second);
        // note that slopes are distinct and decrease
        return D(c.second - b.second) / (c.first - b.first) >= D(b.second - a.second) / (b.first - a.first);
    }

    inline T f(const std::pair<T, T>& l, T x) { return l.first * x + l.second; }
};

#line 2 "src/datastructure/ConvexHullTrick.hpp"
#include <cassert>
#include <queue>

template <typename T, bool isMin = true> struct ConvexHullTrick {
    std::deque<std::pair<T, T>> lines;  // slope decreases as index increases

    bool empty() const { return lines.empty(); }

    void add(T a, T b) {
        if (!isMin) a *= -1, b *= -1;
        std::pair<T, T> l(a, b);
        if (empty()) {
            lines.emplace_back(a, b);
            return;
        }
        if (lines.front().first <= a) {
            if (lines.front().first == a) {
                if (lines.front().second <= b) return;
                lines.pop_front();
            }
            while (lines.size() >= 2 && check(l, lines.front(), lines[1])) lines.pop_front();
            lines.emplace_front(l);
        } else if (a <= lines.back().first) {
            if (lines.back().first == a) {
                if (lines.back().second <= b) return;
                lines.pop_back();
            }
            while (lines.size() >= 2 && check(lines[lines.size() - 2], lines.back(), l)) lines.pop_back();
            lines.emplace_back(l);
        } else
            assert(false);
    }

    T query(T x) {
        assert(!called_query_monotonic_inc && !called_query_monotonic_dec);
        assert(!empty());
        called_query = true;
        int lb = -1, ub = lines.size() - 1;
        while (ub - lb > 1) {
            int mid = (ub + lb) >> 1;
            (f(lines[mid], x) >= f(lines[mid + 1], x) ? lb : ub) = mid;
        }
        T res = f(lines[ub], x);
        return isMin ? res : -res;
    }

    T query_monotone_inc(T x) {
        assert(!called_query && !called_query_monotonic_dec);
        assert(!empty());
        if (!called_query_monotonic_inc)
            called_query_monotonic_inc = true;
        else
            assert(prev_query <= x);
        prev_query = x;
        while (lines.size() >= 2 && f(lines.front(), x) >= f(lines[1], x)) lines.pop_front();
        T res = f(lines.front(), x);
        return isMin ? res : -res;
    }

    T query_monotone_dec(T x) {
        assert(!called_query && !called_query_monotonic_inc);
        assert(!empty());
        if (!called_query_monotonic_dec)
            called_query_monotonic_dec = true;
        else
            assert(x <= prev_query);
        prev_query = x;
        while (lines.size() >= 2 && f(lines.back(), x) >= f(lines[lines.size() - 2], x)) lines.pop_back();
        T res = f(lines.back(), x);
        return isMin ? res : -res;
    }

  private:
    bool called_query = false, called_query_monotonic_inc = false, called_query_monotonic_dec = false;
    T prev_query;

    using D = long double;

    // check if b is unnecessary
    inline bool check(const std::pair<T, T>& a, const std::pair<T, T>& b, const std::pair<T, T>& c) {
        // return (b.first - a.first) * (c.second - b.second) >= (c.first - b.first) * (b.second - a.second);
        // note that slopes are distinct and decrease
        return D(c.second - b.second) / (c.first - b.first) >= D(b.second - a.second) / (b.first - a.first);
    }

    inline T f(const std::pair<T, T>& l, T x) { return l.first * x + l.second; }
};

Back to top page