Line Container (CHT) (src/data-structure/LineContainer.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-07-28 02:25:06+09:00
• Include: #include "src/data-structure/LineContainer.hpp"

• 参考実装：kactl

使い方

$1$ 次関数の追加と，ある $x$ における最大値の取得が $O(\log n)$ / クエリ で行えるデータ構造です．

• LineContainer()：空の LineContainer を作る
• void add(ll a, ll b)：$1$ 次関数 $ax + b$ を追加する
• ll max(ll x)：ある $x$ における最大値を求める

時間計算量: 追加された直線の本数を $n$ として，$O(\log n)$ / クエリ

実装について

• Line::p は，この直線が最大値を取ることのできる最大の $x$ を切り捨てた値です．整数除算によって直線が要るかどうか判断しているため，(max(x) の値がオーバーフローしないのであれば) $|a|, |b| \le 10^{18}$ の直線を追加してもオーバーフローの心配はありません．
• 実装の解説 : Line Container (単調性のない CHT) をソラ書きしよう！ – HackMD (@tatyam)

Verified with

• test/data-structure/LineContainer.test.cpp

Code

struct Line {
   mutable ll a, b, p;
   bool operator<(Line o) const { return a < o.a; }
   bool operator<(ll x) const { return p < x; }
};
// for doubles, use INFINITY and div(a,b) = a/b
struct LineContainer : set<Line, less<>> {
   // floored division (b > 0)
   ll div(ll a, ll b) { return a / b - (a % b < 0); }
   bool check(auto x, auto y) {
      x->p = div(x->b - y->b, y->a - x->a);
      return x->p >= y->p;
   }
   void add(ll a, ll b) {  // add line ax + b
      auto [z, f] = emplace(a, b, LLONG_MAX);
      chmax(z->b, b);
      auto y = z++, x = y;
      while(z != end() && check(y, z)) z = erase(z);
      if(x != begin() && check(--x, y)) check(x, y = erase(y));
      while((y = x) != begin() && (--x)->p >= y->p) check(x, erase(y));
   }
   ll max(ll x) {
      assert(size());
      auto l = *lower_bound(x);
      return l.a * x + l.b;
   }
};

#line 1 "src/data-structure/LineContainer.hpp"
struct Line {
   mutable ll a, b, p;
   bool operator<(Line o) const { return a < o.a; }
   bool operator<(ll x) const { return p < x; }
};
// for doubles, use INFINITY and div(a,b) = a/b
struct LineContainer : set<Line, less<>> {
   // floored division (b > 0)
   ll div(ll a, ll b) { return a / b - (a % b < 0); }
   bool check(auto x, auto y) {
      x->p = div(x->b - y->b, y->a - x->a);
      return x->p >= y->p;
   }
   void add(ll a, ll b) {  // add line ax + b
      auto [z, f] = emplace(a, b, LLONG_MAX);
      chmax(z->b, b);
      auto y = z++, x = y;
      while(z != end() && check(y, z)) z = erase(z);
      if(x != begin() && check(--x, y)) check(x, y = erase(y));
      while((y = x) != begin() && (--x)->p >= y->p) check(x, erase(y));
   }
   ll max(ll x) {
      assert(size());
      auto l = *lower_bound(x);
      return l.a * x + l.b;
   }
};

Back to top page