Nonlinear Convex Hull Trick
(data-structure/cht/nonlinear_convex_hull_trick.hpp)

• View this file on GitHub
• Last update: 2024-12-20 23:39:16+09:00
• Include: #include "data-structure/cht/nonlinear_convex_hull_trick.hpp"

Description

互いにたかだか 1 回しか交わらない関数の集合への追加クエリと最小値取得クエリを処理する．

追加クエリは次の意味での単調性を満たす必要がある：最も新しく追加された関数は，十分大きな $x$ において，集合内の関数の中で最小値を取る．

空間計算量: $O(n)$

Operations

• void add(F f)
  • 関数 $f$ を集合に追加する
  • 時間計算量: $\mathrm{amortized}\ O(\log n)$
• T get(T x)
  • 与えられた $x$ に対し，最小値を取る関数の値を求める
  • 時間計算量: $\mathrm{amortized}\ O(1)$

Reference

• verify: https://atcoder.jp/contests/abc373/submissions/58145171

Code

#pragma once
#include <algorithm>
#include <deque>
#include <utility>

template <typename T, typename F, T (*eval)(F, T)>
class NonlinearConvexHullTrick {
   public:
    NonlinearConvexHullTrick(T lb, T ub) : lb(lb), ub(ub) {}

    void add(const F& f) {
        T x = lb;
        while (funcs.size() >= 2 &&
               funcs.back().second >=
                   (x = intersection(funcs.back().first, f))) {
            funcs.pop_back();
        }
        if (funcs.size() == 1) x = intersection(funcs.back().first, f);
        funcs.push_back({f, x});
    }

    T get(T x) {
        while (funcs.size() >= 2 &&
               eval(funcs.front().first, x) > eval(funcs[1].first, x)) {
            funcs.pop_front();
        }
        funcs.front().second = lb;
        return eval(funcs.front().first, x);
    }

   private:
    // pair (function, intersection with the previous function)
    std::deque<std::pair<F, T>> funcs;
    T lb, ub;

    // smallest x s.t. f1(x) >= f2(x)
    T intersection(const F& f1, const F& f2) {
        T l = lb - 1, r = ub + 1;
        while (r - l > 1) {
            T m = std::midpoint(l, r);
            if (eval(f1, m) < eval(f2, m)) {
                l = m;
            } else {
                r = m;
            }
        }
        return r;
    }
};

#line 2 "data-structure/cht/nonlinear_convex_hull_trick.hpp"
#include <algorithm>
#include <deque>
#include <utility>

template <typename T, typename F, T (*eval)(F, T)>
class NonlinearConvexHullTrick {
   public:
    NonlinearConvexHullTrick(T lb, T ub) : lb(lb), ub(ub) {}

    void add(const F& f) {
        T x = lb;
        while (funcs.size() >= 2 &&
               funcs.back().second >=
                   (x = intersection(funcs.back().first, f))) {
            funcs.pop_back();
        }
        if (funcs.size() == 1) x = intersection(funcs.back().first, f);
        funcs.push_back({f, x});
    }

    T get(T x) {
        while (funcs.size() >= 2 &&
               eval(funcs.front().first, x) > eval(funcs[1].first, x)) {
            funcs.pop_front();
        }
        funcs.front().second = lb;
        return eval(funcs.front().first, x);
    }

   private:
    // pair (function, intersection with the previous function)
    std::deque<std::pair<F, T>> funcs;
    T lb, ub;

    // smallest x s.t. f1(x) >= f2(x)
    T intersection(const F& f1, const F& f2) {
        T l = lb - 1, r = ub + 1;
        while (r - l > 1) {
            T m = std::midpoint(l, r);
            if (eval(f1, m) < eval(f2, m)) {
                l = m;
            } else {
                r = m;
            }
        }
        return r;
    }
};

Back to top page