convex/lichao.hpp

• View this file on GitHub
• Last update: 2024-01-14 14:14:47+09:00
• Include: #include "convex/lichao.hpp"

Verified with

• test/library_checker/datastructure/line_add_get_min_lichao_2.test.cpp
• test/library_checker/datastructure/segment_add_get_min_2.test.cpp
• test/yukicoder/1867.test.cpp
• test/yukicoder/705_2.test.cpp

Code

/*
struct F {
  using value_type = ll;  // operator() の戻り値
  int a;
  ll b;
  ll operator()(ll x) { return a * x + b; }
};
*/

// 評価点は ll
// FUNC f には T operator() を定義する, T は比較可能な型
// 1次式：FUNC = LiChaoTree_Line
template <typename FUNC, bool COMPRESS, bool MINIMIZE>
struct LiChao_Tree {
  using T = typename FUNC::value_type;
  vc<ll> X;
  ll lo, hi;
  vc<FUNC> dat;
  int n, log, size;

  inline int get_idx(ll x) {
    if constexpr (COMPRESS) { return LB(X, x); }
    assert(lo <= x && x <= hi);
    return x - lo;
  }

  template <typename XY>
  LiChao_Tree(const vc<XY>& pts, FUNC default_fn) {
    static_assert(COMPRESS);
    for (auto&& x: pts) X.eb(x);
    UNIQUE(X);
    n = len(X), log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, default_fn);
  }

  LiChao_Tree(ll lo, ll hi, FUNC default_fn) : lo(lo), hi(hi) {
    static_assert(!COMPRESS);
    n = hi - lo, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, default_fn);
  }

  void add_line(FUNC f) { return add_line_at(1, f); }

  void add_segment(ll xl, ll xr, FUNC f) {
    xl = get_idx(xl), xr = get_idx(xr);
    xl += size, xr += size;
    while (xl < xr) {
      if (xl & 1) add_line_at(xl++, f);
      if (xr & 1) add_line_at(--xr, f);
      xl >>= 1, xr >>= 1;
    }
  }

  // 最適な値と FUNC の pair
  pair<T, FUNC> query(ll x) {
    FUNC f = dat[0]; // default_fn
    T fx = f(x);
    int i = get_idx(x) + size;
    while (i) {
      FUNC g = dat[i];
      T gx = g(x);
      if ((MINIMIZE && gx < fx) || (!MINIMIZE && gx > fx)) { f = g, fx = gx; }
      i >>= 1;
    }
    return {fx, f};
  }

  void add_line_at(int i, FUNC f) {
    int upper_bit = 31 - __builtin_clz(i);
    int l = (size >> upper_bit) * (i - (1 << upper_bit));
    int r = l + (size >> upper_bit);
    while (l < r) {
      FUNC g = dat[i];
      T fl = evaluate_inner(f, l), fr = evaluate_inner(f, r - 1);
      T gl = evaluate_inner(g, l), gr = evaluate_inner(g, r - 1);
      bool bl = (MINIMIZE ? fl < gl : fl > gl);
      bool br = (MINIMIZE ? fr < gr : fr > gr);
      if (bl && br) {
        dat[i] = f;
        return;
      }
      if (!bl && !br) return;
      int m = (l + r) / 2;
      T fm = evaluate_inner(f, m), gm = evaluate_inner(g, m);
      bool bm = (MINIMIZE ? fm < gm : fm > gm);
      if (bm) {
        dat[i] = f;
        f = g;
        if (!bl) { i = 2 * i + 0, r = m; }
        if (bl) { i = 2 * i + 1, l = m; }
      }
      if (!bm) {
        if (bl) { i = 2 * i + 0, r = m; }
        if (!bl) { i = 2 * i + 1, l = m; }
      }
    }
  }

private:
  inline T evaluate_inner(FUNC& f, ll x) {
    return f((COMPRESS ? X[min<int>(x, n - 1)] : min<int>(x + lo, hi - 1)));
  }
};

#line 1 "convex/lichao.hpp"
/*
struct F {
  using value_type = ll;  // operator() の戻り値
  int a;
  ll b;
  ll operator()(ll x) { return a * x + b; }
};
*/

// 評価点は ll
// FUNC f には T operator() を定義する, T は比較可能な型
// 1次式：FUNC = LiChaoTree_Line
template <typename FUNC, bool COMPRESS, bool MINIMIZE>
struct LiChao_Tree {
  using T = typename FUNC::value_type;
  vc<ll> X;
  ll lo, hi;
  vc<FUNC> dat;
  int n, log, size;

  inline int get_idx(ll x) {
    if constexpr (COMPRESS) { return LB(X, x); }
    assert(lo <= x && x <= hi);
    return x - lo;
  }

  template <typename XY>
  LiChao_Tree(const vc<XY>& pts, FUNC default_fn) {
    static_assert(COMPRESS);
    for (auto&& x: pts) X.eb(x);
    UNIQUE(X);
    n = len(X), log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, default_fn);
  }

  LiChao_Tree(ll lo, ll hi, FUNC default_fn) : lo(lo), hi(hi) {
    static_assert(!COMPRESS);
    n = hi - lo, log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, default_fn);
  }

  void add_line(FUNC f) { return add_line_at(1, f); }

  void add_segment(ll xl, ll xr, FUNC f) {
    xl = get_idx(xl), xr = get_idx(xr);
    xl += size, xr += size;
    while (xl < xr) {
      if (xl & 1) add_line_at(xl++, f);
      if (xr & 1) add_line_at(--xr, f);
      xl >>= 1, xr >>= 1;
    }
  }

  // 最適な値と FUNC の pair
  pair<T, FUNC> query(ll x) {
    FUNC f = dat[0]; // default_fn
    T fx = f(x);
    int i = get_idx(x) + size;
    while (i) {
      FUNC g = dat[i];
      T gx = g(x);
      if ((MINIMIZE && gx < fx) || (!MINIMIZE && gx > fx)) { f = g, fx = gx; }
      i >>= 1;
    }
    return {fx, f};
  }

  void add_line_at(int i, FUNC f) {
    int upper_bit = 31 - __builtin_clz(i);
    int l = (size >> upper_bit) * (i - (1 << upper_bit));
    int r = l + (size >> upper_bit);
    while (l < r) {
      FUNC g = dat[i];
      T fl = evaluate_inner(f, l), fr = evaluate_inner(f, r - 1);
      T gl = evaluate_inner(g, l), gr = evaluate_inner(g, r - 1);
      bool bl = (MINIMIZE ? fl < gl : fl > gl);
      bool br = (MINIMIZE ? fr < gr : fr > gr);
      if (bl && br) {
        dat[i] = f;
        return;
      }
      if (!bl && !br) return;
      int m = (l + r) / 2;
      T fm = evaluate_inner(f, m), gm = evaluate_inner(g, m);
      bool bm = (MINIMIZE ? fm < gm : fm > gm);
      if (bm) {
        dat[i] = f;
        f = g;
        if (!bl) { i = 2 * i + 0, r = m; }
        if (bl) { i = 2 * i + 1, l = m; }
      }
      if (!bm) {
        if (bl) { i = 2 * i + 0, r = m; }
        if (!bl) { i = 2 * i + 1, l = m; }
      }
    }
  }

private:
  inline T evaluate_inner(FUNC& f, ll x) {
    return f((COMPRESS ? X[min<int>(x, n - 1)] : min<int>(x + lo, hi - 1)));
  }
};

Back to top page