Li-Chao-Tree (src/Optimization/LiChaoTree.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-11-27 13:00:48+09:00
Include: #include "src/Optimization/LiChaoTree.hpp"

( 例えば一次関数などの ) 高々一点で交わる $x$ の関数の集合

$\displaystyle f_i(x) = f(x; \boldsymbol{p}^{(i)})= f(x;p^{(i)}_0,\dots,p^{(i)}_n) $

を扱うデータ構造.
浮動小数点数もいけるはず.
2点以上で交わる可能性がある関数の集合を挿入した時の動作は未定義.
クラステンプレートは推論させる.

使用例

宣言

auto f = [](long long x, int a, int b){return a * x + b;}; // ax+b
LiChaoTree lct(f);
auto tree = lct.make_tree<MINIMIZE>();

クエリ

tree.insert(2, 3); // 2x+3
tree.insert(1, 1, 0, 2); // x+1 (0<= x < 2)
auto [val1, id1] = tree.query(1);
cout << val1 << " "<< id1 << '\n'; // 2 1
auto [val2, id2] = tree.query(-1);
cout << val2 << " "<< id2 << '\n'; // 1 0

`LiChaoTree` クラス

まず初期化のために触るクラス.
内部で関数やパラメータを格納したりの役割がある.

メンバ関数	概要
`LiChaoTree(f, LB, UB)`	コンストラクタ. $x$ の関数 $f(x;p_0,\dots,p_n)$ を渡す. クエリ引数 $x$ の収まる範囲を半開区間 $\lbrack \mathrm{LB}, \mathrm{UB})$ で渡す. ( デフォルトは `LB=-2e9`, `UB=2e9`)
`make_tree<sgn, persistent>()`	`LiChaoTreeInterface` クラスのオブジェクトを返す. 何も関数が挿入されていない空のデータ構造を返す. template 第一引数で最小か最大を指定する. (デフォルトは最小) template 第二引数が true なら永続化. (デフォルトはfalse)

`LiChaoTreeInterface` クラス

メインで触ることになるもの.

メンバ関数	概要	計算量
`insert(p_0,...,p_n)`	関数 $f(x;p_0,\dots,p_n)$ を挿入.	$O(\log n)$
`insert(p_0,...,p_n,l)`	半開区間制約付きの関数 $f(x;p_0,\dots,p_n) \hspace{1mm}x\in\lbrack l,\mathrm{UB}) $ を挿入.	$O((\log n)^2)$
`insert(p_0,...,p_n,l,r)`	半開区間制約付きの関数 $f(x;p_0,\dots,p_n) \hspace{1mm}x\in\lbrack l,r) $ を挿入.	$O((\log n)^2)$
`query(x)`	{ $x$ における最小値(最大値), それを達成する関数の番号 } を返す. 存在しない場合 { 未定義, -1 } を返す.	$O(\log n)$
`parms(i)`	$i$ 番目の関数のパラメータを返す．	$O(1)$

Verify

Kyoto University Programming Contest 2019 L - タケノコ (永続)
AtCoder Regular Contest 051 D - 長方形 (doubleでac)
Yandex Contest Алгоритм 2022 K. Stepwise subsequence (有理数クラス, doubleでac)
COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君
技術室奥プログラミングコンテスト#2 F - NPCの家 (NPC’s House)

Depends on

Verified with

Code

#pragma once
#include <limits>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cassert>
#include "src/Internal/function_traits.hpp"
#include "src/Optimization/MinMaxEnum.hpp"
template <class F, class T> class LiChaoTree {};
template <class F, class T, class... Prms> class LiChaoTree<F, std::tuple<T, Prms...>> {
 using R= result_type_t<F>;
 F f;
 const T LB, UB;
 std::vector<std::tuple<Prms...>> ps;
 template <MinMaxEnum sgn, bool persistent> class LiChaoTreeInterface {
  LiChaoTree *ins;
  struct Node {
   int id= -1;
   Node *ch[2]= {nullptr, nullptr};
  } *root;
  inline R eval(int id, T x) const { return std::apply(ins->f, std::tuple_cat(std::make_tuple(x), ins->ps[id])); }
  static inline bool cmp(const R &p, const R &n, int pi, int ni) {
   if constexpr (sgn == MINIMIZE) return p > n || (p == n && pi > ni);
   else return p < n || (p == n && pi > ni);
  }
  inline bool cmp(T x, int pi, int ni) const {
   if (ni == -1) return false;
   if (pi == -1) return true;
   return cmp(eval(pi, x), eval(ni, x), pi, ni);
  }
  static inline T ub(T r) {
   if constexpr (std::is_floating_point_v<T>) return r;
   else return r - 1;
  }
  inline void addl(Node *&t, int id, T xl, T xr) {
   if (!t) return t= new Node{id}, void();
   bool bl= cmp(xl, t->id, id), br= cmp(ub(xr), t->id, id);
   if (!bl && !br) return;
   if constexpr (persistent) t= new Node(*t);
   if (bl && br) return t->id= id, void();
   T xm= (xl + xr) / 2;
   if (cmp(xm, t->id, id)) std::swap(t->id, id), bl= !bl;
   if constexpr (std::is_floating_point_v<T>)
    if (xr - xl < 1e-9) return;
   bl ? addl(t->ch[0], id, xl, xm) : addl(t->ch[1], id, xm, xr);
  }
  inline void adds(Node *&t, int id, T l, T r, T xl, T xr) {
   if (r <= xl || xr <= l) return;
   if (l <= xl && xr <= r) return addl(t, id, xl, xr);
   if (!t) t= new Node;
   else if constexpr (persistent) t= new Node(*t);
   T xm= (xl + xr) / 2;
   adds(t->ch[0], id, l, r, xl, xm), adds(t->ch[1], id, l, r, xm, xr);
  }
  inline std::pair<R, int> query(const Node *t, T x, T xl, T xr) const {
   if (!t) return {R(), -1};
   T xm= (xl + xr) / 2;
   auto b= x < xm ? query(t->ch[0], x, xl, xm) : query(t->ch[1], x, xm, xr);
   if (t->id == -1) return b;
   R a= eval(t->id, x);
   return b.second != -1 && cmp(a, b.first, t->id, b.second) ? b : std::make_pair(a, t->id);
  }
 public:
  LiChaoTreeInterface()= default;
  LiChaoTreeInterface(LiChaoTree *ins): ins(ins), root(nullptr) {}
  void insert(const Prms &...args) { ins->ps.emplace_back(args...), addl(root, ins->ps.size() - 1, ins->LB, ins->UB); }
  // [l, r)
  void insert(const Prms &...args, T l, T r) {
   l= std::max(l, ins->LB), r= std::min(r, ins->UB);
   if (l < r) ins->ps.emplace_back(args...), adds(root, ins->ps.size() - 1, l, r, ins->LB, ins->UB);
  }
  // [l, UB)
  void insert(const Prms &...args, T l) { insert(args..., l, ins->UB); }
  std::pair<R, int> query(T x) const { return assert(ins->LB <= x && x < ins->UB), query(root, x, ins->LB, ins->UB); }
  const std::tuple<Prms...> &params(int id) const { return ins->ps[id]; }
 };
public:
 LiChaoTree(const F &f, T LB= -2e9, T UB= 2e9): f(f), LB(LB), UB(UB) {}
 template <MinMaxEnum sgn= MINIMIZE, bool persistent= false> LiChaoTreeInterface<sgn, persistent> make_tree() { return this; }
};
template <class F, class T, class U> LiChaoTree(F, T, U) -> LiChaoTree<F, argument_type_t<F>>;
template <class F, class T> LiChaoTree(F, T) -> LiChaoTree<F, argument_type_t<F>>;
template <class F> LiChaoTree(F) -> LiChaoTree<F, argument_type_t<F>>;

#line 2 "src/Optimization/LiChaoTree.hpp"
#include <limits>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/LiChaoTree.hpp"
template <class F, class T> class LiChaoTree {};
template <class F, class T, class... Prms> class LiChaoTree<F, std::tuple<T, Prms...>> {
 using R= result_type_t<F>;
 F f;
 const T LB, UB;
 std::vector<std::tuple<Prms...>> ps;
 template <MinMaxEnum sgn, bool persistent> class LiChaoTreeInterface {
  LiChaoTree *ins;
  struct Node {
   int id= -1;
   Node *ch[2]= {nullptr, nullptr};
  } *root;
  inline R eval(int id, T x) const { return std::apply(ins->f, std::tuple_cat(std::make_tuple(x), ins->ps[id])); }
  static inline bool cmp(const R &p, const R &n, int pi, int ni) {
   if constexpr (sgn == MINIMIZE) return p > n || (p == n && pi > ni);
   else return p < n || (p == n && pi > ni);
  }
  inline bool cmp(T x, int pi, int ni) const {
   if (ni == -1) return false;
   if (pi == -1) return true;
   return cmp(eval(pi, x), eval(ni, x), pi, ni);
  }
  static inline T ub(T r) {
   if constexpr (std::is_floating_point_v<T>) return r;
   else return r - 1;
  }
  inline void addl(Node *&t, int id, T xl, T xr) {
   if (!t) return t= new Node{id}, void();
   bool bl= cmp(xl, t->id, id), br= cmp(ub(xr), t->id, id);
   if (!bl && !br) return;
   if constexpr (persistent) t= new Node(*t);
   if (bl && br) return t->id= id, void();
   T xm= (xl + xr) / 2;
   if (cmp(xm, t->id, id)) std::swap(t->id, id), bl= !bl;
   if constexpr (std::is_floating_point_v<T>)
    if (xr - xl < 1e-9) return;
   bl ? addl(t->ch[0], id, xl, xm) : addl(t->ch[1], id, xm, xr);
  }
  inline void adds(Node *&t, int id, T l, T r, T xl, T xr) {
   if (r <= xl || xr <= l) return;
   if (l <= xl && xr <= r) return addl(t, id, xl, xr);
   if (!t) t= new Node;
   else if constexpr (persistent) t= new Node(*t);
   T xm= (xl + xr) / 2;
   adds(t->ch[0], id, l, r, xl, xm), adds(t->ch[1], id, l, r, xm, xr);
  }
  inline std::pair<R, int> query(const Node *t, T x, T xl, T xr) const {
   if (!t) return {R(), -1};
   T xm= (xl + xr) / 2;
   auto b= x < xm ? query(t->ch[0], x, xl, xm) : query(t->ch[1], x, xm, xr);
   if (t->id == -1) return b;
   R a= eval(t->id, x);
   return b.second != -1 && cmp(a, b.first, t->id, b.second) ? b : std::make_pair(a, t->id);
  }
 public:
  LiChaoTreeInterface()= default;
  LiChaoTreeInterface(LiChaoTree *ins): ins(ins), root(nullptr) {}
  void insert(const Prms &...args) { ins->ps.emplace_back(args...), addl(root, ins->ps.size() - 1, ins->LB, ins->UB); }
  // [l, r)
  void insert(const Prms &...args, T l, T r) {
   l= std::max(l, ins->LB), r= std::min(r, ins->UB);
   if (l < r) ins->ps.emplace_back(args...), adds(root, ins->ps.size() - 1, l, r, ins->LB, ins->UB);
  }
  // [l, UB)
  void insert(const Prms &...args, T l) { insert(args..., l, ins->UB); }
  std::pair<R, int> query(T x) const { return assert(ins->LB <= x && x < ins->UB), query(root, x, ins->LB, ins->UB); }
  const std::tuple<Prms...> &params(int id) const { return ins->ps[id]; }
 };
public:
 LiChaoTree(const F &f, T LB= -2e9, T UB= 2e9): f(f), LB(LB), UB(UB) {}
 template <MinMaxEnum sgn= MINIMIZE, bool persistent= false> LiChaoTreeInterface<sgn, persistent> make_tree() { return this; }
};
template <class F, class T, class U> LiChaoTree(F, T, U) -> LiChaoTree<F, argument_type_t<F>>;
template <class F, class T> LiChaoTree(F, T) -> LiChaoTree<F, argument_type_t<F>>;
template <class F> LiChaoTree(F) -> LiChaoTree<F, argument_type_t<F>>;