test/unittest/li-chao-tree.test.cpp

View this file on GitHub
Last update: 2026-08-10 15:44:16+00:00

Depends on

Code

// competitive-verifier: STANDALONE

#include "../../template/template.hpp"

#include "../../structure/convex-hull-trick/li-chao-tree.hpp"

namespace {

using int64 = long long;

constexpr int64 INF = 4'000'000'000'000'000'000LL;

void check(const vector<int64>& coordinates,
           const vector<pair<int64, int64>>& lines) {
  LiChaoTree<int64> tree(coordinates, INF);
  for (auto [a, b] : lines) tree.update(a, b);

  vector<int64> xs = coordinates;
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  for (int i = 0; i < (int)xs.size(); i++) {
    int64 expected = INF;
    for (auto [a, b] : lines) expected = min(expected, a * xs[i] + b);
    assert(tree.query(i) == expected);
  }
}

}  // namespace

int main() {
  check({5, -3, 5, 1, -3}, {{2, 4}, {-1, 7}, {0, -2}});
  check({42, 42, 42}, {});
  check({42, 42, 42}, {{-3, 100}, {2, -100}});
  check({numeric_limits<int64>::max(), -1, 0}, {{0, 5}, {0, -3}});

  mt19937_64 rng(123456789);
  for (int rep = 0; rep < 500; rep++) {
    int n = 1 + rng() % 30;
    vector<int64> coordinates(n);
    for (auto& x : coordinates) x = (int64)(rng() % 21) - 10;
    shuffle(begin(coordinates), end(coordinates), rng);

    int m = rng() % 30;
    vector<pair<int64, int64>> lines(m);
    for (auto& [a, b] : lines) {
      a = (int64)(rng() % 21) - 10;
      b = (int64)(rng() % 101) - 50;
    }
    check(coordinates, lines);
  }
}

#line 1 "test/unittest/li-chao-tree.test.cpp"
// competitive-verifier: STANDALONE

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}
#line 4 "test/unittest/li-chao-tree.test.cpp"

#line 2 "structure/convex-hull-trick/li-chao-tree.hpp"

#line 7 "structure/convex-hull-trick/li-chao-tree.hpp"

template <typename T>
struct LiChaoTree {
  struct Line {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    inline T get(T x) const { return a * x + b; }

    inline bool over(const Line& b, const T& x) const {
      return get(x) < b.get(x);
    }
  };

  std::vector<T> xs;
  std::vector<Line> seg;
  int sz;

  LiChaoTree(const std::vector<T>& x, T INF) : xs(x) {
    std::sort(std::begin(xs), std::end(xs));
    xs.erase(std::unique(std::begin(xs), std::end(xs)), std::end(xs));
    sz = 1;
    while (sz < (int)xs.size()) sz <<= 1;
    while ((int)xs.size() < sz) xs.push_back(xs.back());
    seg.assign(2 * sz - 1, Line(0, INF));
  }

  void update(Line& x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
    if (malta) std::swap(seg[k], x);
    if (l + 1 >= r)
      return;
    else if (latte != malta)
      update(x, 2 * k + 1, l, mid);
    else
      update(x, 2 * k + 2, mid, r);
  }

  void update(T a, T b) {  // ax+b
    Line l(a, b);
    update(l, 0, 0, sz);
  }

  T query(int k) {  // xs[k]
    const T x = xs[k];
    k += sz - 1;
    T ret = seg[k].get(x);
    while (k > 0) {
      k = (k - 1) >> 1;
      ret = std::min(ret, seg[k].get(x));
    }
    return ret;
  }
};
#line 6 "test/unittest/li-chao-tree.test.cpp"

namespace {

using int64 = long long;

constexpr int64 INF = 4'000'000'000'000'000'000LL;

void check(const vector<int64>& coordinates,
           const vector<pair<int64, int64>>& lines) {
  LiChaoTree<int64> tree(coordinates, INF);
  for (auto [a, b] : lines) tree.update(a, b);

  vector<int64> xs = coordinates;
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  for (int i = 0; i < (int)xs.size(); i++) {
    int64 expected = INF;
    for (auto [a, b] : lines) expected = min(expected, a * xs[i] + b);
    assert(tree.query(i) == expected);
  }
}

}  // namespace

int main() {
  check({5, -3, 5, 1, -3}, {{2, 4}, {-1, 7}, {0, -2}});
  check({42, 42, 42}, {});
  check({42, 42, 42}, {{-3, 100}, {2, -100}});
  check({numeric_limits<int64>::max(), -1, 0}, {{0, 5}, {0, -3}});

  mt19937_64 rng(123456789);
  for (int rep = 0; rep < 500; rep++) {
    int n = 1 + rng() % 30;
    vector<int64> coordinates(n);
    for (auto& x : coordinates) x = (int64)(rng() % 21) - 10;
    shuffle(begin(coordinates), end(coordinates), rng);

    int m = rng() % 30;
    vector<pair<int64, int64>> lines(m);
    for (auto& [a, b] : lines) {
      a = (int64)(rng() % 21) - 10;
      b = (int64)(rng() % 101) - 50;
    }
    check(coordinates, lines);
  }
}