cpp-library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub shino16/cpp-library

:warning: ds/cht.hpp

Depends on

Code

#pragma once
#include "arith/sqrt.hpp"
#include "la/vec.hpp"
#include "num/int/bisect.hpp"

template <class T>
using linear_fn = pair<T, T>;

template <class T>
T apply(linear_fn<T> f, T x) {
  return f.first * x + f.second;
}

// checked (CF 660F)

// min/max of linear functions
template <class T, bool Maximize = false>
class convex_hull_trick {
 public:
  convex_hull_trick() : ready(true), hull({linear_fn<T>{0, sentinel()}}) {}
  template <class It>
  convex_hull_trick(It first, It last) {
    init(first, last);
  }
  void clear() {
    hull.clear(), edges.clear();
    hull.emplace_back(0, sentinel());
  }
  template <bool Sorted = false, class It>
  void init(It first, It last) {
    clear();
    int n = distance(first, last);
    hull.reserve(n + 1), edges.reserve(n);
    if (!Sorted) sort(first, last);
    for (auto it = first; it != last; it++) {
      while (!edges.empty() &&
             (det(edges.back(), *it - hull.back()) <= 0) ^ Maximize)
        hull.pop_back(), edges.pop_back();
      edges.push_back(*it - hull.back()), hull.push_back(*it);
    }
    ready = true;
  }
  void rebuild() {
    vector<linear_fn<T>> fs(all(hull));
    fs.insert(fs.end(), all(aux));
    sort(all(fs));
    init(all(fs));
  }

  void add(linear_fn<T> f) { aux.push_back(f), ready = false; }
  void add(T a, T b) { aux.emplace_back(a, b), ready = false; }

  T apply(T x) {
    assert(ready);
    linear_fn<T> f(1, -x);
    int i = bisect<int>(0, edges.size(), [&](int j) {
      return (det(f, edges[j]) < 0) ^ Maximize;
    });
    T ans = ::apply(hull[i], x);
    for (auto g : aux) ans = min(ans, ::apply(g, x));
    return ans;
  }

 private:
  bool ready;
  vector<linear_fn<T>> hull, edges, aux;
  static T sentinel() {
    return floor_sqrt(numeric_limits<T>::max()) * (Maximize ? -1 : 1);
  }
};

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "arith/sqrt.hpp"

template <class T, enable_if_t<sizeof(T) <= 8>* = nullptr>
constexpr T floor_sqrt(T x) {
  if (x == 0) return 0;
  T s = round(sqrt(x));
  return (s + x / s) / 2;
}

template <class T, enable_if_t<sizeof(T) <= 8>* = nullptr>
constexpr T ceil_sqrt(T x) {
  return x == 0 ? 0 : floor_sqrt(x - 1) + 1;
}
#line 3 "la/vec.hpp"

template <class T, class U, class F, size_t... Is>
void zip_with_impl(T&& a, U&& b, F f, index_sequence<Is...>) {
  (f(get<Is>(a), get<Is>(b)), ...);
}

template <class T, class U, class F>
void zip_with(T&& a, U&& b, F f) {
  zip_with_impl(
      forward<T>(a), forward<U>(b), f,
      make_index_sequence<tuple_size_v<decay_t<T>>>{});
}

template <
    class T, class U,
    enable_if_t<tuple_size<T>::value == tuple_size<U>::value>* = nullptr>
T& operator+=(T& a, const U& b) {
  zip_with(a, b, [](auto&& x, auto&& y) { x += y; });
  return a;
}

template <
    class T, class U,
    enable_if_t<tuple_size<T>::value == tuple_size<U>::value>* = nullptr>
T& operator-=(T& a, const U& b) {
  zip_with(a, b, [](auto&& x, auto&& y) { x -= y; });
  return a;
}

template <class T, class U>
T& operator*=(T& a, U r) {
  for_each(all(a), [=](auto& x) { x *= r; });
  return a;
}

template <
    class T, class U,
    enable_if_t<tuple_size<T>::value == tuple_size<U>::value>* = nullptr>
T operator+(const T& a, const U& b) {
  T c(a);
  c += b;
  return c;
}

template <
    class T, class U,
    enable_if_t<tuple_size<T>::value == tuple_size<U>::value>* = nullptr>
T operator-(const T& a, const U& b) {
  T c(a);
  c -= b;
  return c;
}

template <class T, class U>
T operator*(U r, const T& a) {
  T c(a);
  c *= r;
  return c;
}

template <class T, class E = tuple_element_t<0, T>>
E dot(const T& a, const T& b) {
  E res(0);
  zip_with(a, b, [&](auto&& x, auto&& y) { res += x * y; });
  return res;
}

template <class T, enable_if_t<tuple_size_v<T> == 2>* = nullptr>
auto det(const T& a, const T& b) {
  return get<0>(a) * get<1>(b) - get<1>(a) * get<0>(b);
}

// Returns k s.t. a == kb
// k=inf if b == 0
template <class T>
double factor(const T& a, const T& b) {
  double res = numeric_limits<double>::infinity();
  assert(dot(a, b) == 0);
  zip_with(a, b, [&](auto&&x, auto&& y) {
    if (y) res = x / y;
  });
  return res;
}
#line 2 "num/int/bisect.hpp"

template <class I, class F>
I bisect(I l, I r, F p) {
  while (l != r) {
    I m = ((l ^ r) >> 1) + (l & r);
    if (p(m)) l = m + 1;
    else r = m;
  }
  return l;
}
#line 5 "ds/cht.hpp"

template <class T>
using linear_fn = pair<T, T>;

template <class T>
T apply(linear_fn<T> f, T x) {
  return f.first * x + f.second;
}

// checked (CF 660F)

// min/max of linear functions
template <class T, bool Maximize = false>
class convex_hull_trick {
 public:
  convex_hull_trick() : ready(true), hull({linear_fn<T>{0, sentinel()}}) {}
  template <class It>
  convex_hull_trick(It first, It last) {
    init(first, last);
  }
  void clear() {
    hull.clear(), edges.clear();
    hull.emplace_back(0, sentinel());
  }
  template <bool Sorted = false, class It>
  void init(It first, It last) {
    clear();
    int n = distance(first, last);
    hull.reserve(n + 1), edges.reserve(n);
    if (!Sorted) sort(first, last);
    for (auto it = first; it != last; it++) {
      while (!edges.empty() &&
             (det(edges.back(), *it - hull.back()) <= 0) ^ Maximize)
        hull.pop_back(), edges.pop_back();
      edges.push_back(*it - hull.back()), hull.push_back(*it);
    }
    ready = true;
  }
  void rebuild() {
    vector<linear_fn<T>> fs(all(hull));
    fs.insert(fs.end(), all(aux));
    sort(all(fs));
    init(all(fs));
  }

  void add(linear_fn<T> f) { aux.push_back(f), ready = false; }
  void add(T a, T b) { aux.emplace_back(a, b), ready = false; }

  T apply(T x) {
    assert(ready);
    linear_fn<T> f(1, -x);
    int i = bisect<int>(0, edges.size(), [&](int j) {
      return (det(f, edges[j]) < 0) ^ Maximize;
    });
    T ans = ::apply(hull[i], x);
    for (auto g : aux) ans = min(ans, ::apply(g, x));
    return ans;
  }

 private:
  bool ready;
  vector<linear_fn<T>> hull, edges, aux;
  static T sentinel() {
    return floor_sqrt(numeric_limits<T>::max()) * (Maximize ? -1 : 1);
  }
};
Back to top page