tests/li_chao_segtree/line.test.cpp

View this file on GitHub
Last update: 2025-02-10 20:05:30+09:00
Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include "tools/li_chao_segtree.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, Q;
  std::cin >> N >> Q;
  std::vector<ll> a(N), b(N);
  for (ll i = 0; i < N; ++i) {
    std::cin >> a[i] >> b[i];
  }
  std::vector<std::tuple<ll, ll, ll>> queries(Q);
  for (ll i = 0; i < Q; ++i) {
    std::cin >> std::get<0>(queries[i]);
    if (std::get<0>(queries[i]) == 0) {
      std::cin >> std::get<1>(queries[i]) >> std::get<2>(queries[i]);
    } else {
      std::cin >> std::get<1>(queries[i]);
    }
  }

  std::vector<ll> x;
  for (const auto& [t, p, _] : queries) {
    if (t == 1) {
      x.push_back(p);
    }
  }
  std::sort(x.begin(), x.end());
  x.erase(std::unique(x.begin(), x.end()), x.end());
  tools::li_chao_segtree<ll> seg(x.begin(), x.end(), false);

  for (ll i = 0; i < N; ++i) {
    seg.add(a[i], b[i]);
  }
  for (const auto& [t, q1, q2] : queries) {
    if (t == 0) {
      seg.add(q1, q2);
    } else {
      std::cout << seg.query(q1) << '\n';
    }
  }
  return 0;
}

#line 1 "tests/li_chao_segtree/line.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#line 1 "tools/li_chao_segtree.hpp"



#line 5 "tools/li_chao_segtree.hpp"
#include <cstddef>
#include <utility>
#include <limits>
#include <cassert>
#line 10 "tools/li_chao_segtree.hpp"
#include <numeric>
#include <iterator>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/floor_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 1 "tools/ceil_log2.hpp"



#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/lower_bound.hpp"



#line 6 "tools/lower_bound.hpp"

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}


#line 17 "tools/li_chao_segtree.hpp"

namespace tools {
  template <typename T>
  class li_chao_segtree {
  private:
    bool m_maximal;
    ::std::vector<T> m_xs;
    ::std::size_t m_height;
    ::std::vector<::std::pair<T, T>> m_nodes;

    ::std::size_t capacity() const {
      return this->m_nodes.size() / 2;
    }

    bool comp(const T& x, const T& y) const {
      return this->m_maximal ? x < y : y < x;
    }

    void add_impl(T fa, T fb, ::std::size_t node_id) {
      assert(::tools::floor_log2(node_id) <= this->m_height);
      ::std::size_t l = (node_id - ::tools::pow2(::tools::floor_log2(node_id))) * ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      ::std::size_t r = l + ::tools::pow2(this->m_height - ::tools::floor_log2(node_id));
      while (node_id < this->m_nodes.size()) {
        const ::std::size_t m = (l + r) / 2;
        auto& [ga, gb] = this->m_nodes[node_id];
        bool greater_l = this->comp(ga * this->m_xs[l] + gb, fa * this->m_xs[l] + fb);
        bool greater_m = this->comp(ga * this->m_xs[m] + gb, fa * this->m_xs[m] + fb);
        bool greater_r = this->comp(ga * this->m_xs[r] + gb, fa * this->m_xs[r] + fb);
        if (greater_l == greater_m && greater_m == greater_r) {
          if (greater_l) {
            ::std::swap(fa, ga);
            ::std::swap(fb, gb);
          }
          return;
        }
        if (greater_m) {
          ::std::swap(fa, ga);
          ::std::swap(fb, gb);
          greater_l = !greater_l;
          greater_m = !greater_m;
          greater_r = !greater_r;
        }
        if (greater_l) {
          node_id = node_id * 2;
          r = m;
        } else {
          node_id = node_id * 2 + 1;
          l = m;
        }
      }
    }

  public:
    template <typename Iterator>
    li_chao_segtree(const Iterator& begin, const Iterator& end, const bool maximal) :
      m_maximal(maximal),
      m_xs(begin, end),
      m_height(this->m_xs.empty() ? ::std::numeric_limits<T>::min() : ::tools::ceil_log2(this->m_xs.size())),
      m_nodes(this->m_xs.empty() ? 0 : ::tools::pow2(this->m_height + 1), ::std::pair<T, T>(0, maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max())) {
      if (this->m_xs.empty()) return;

      assert(::std::is_sorted(this->m_xs.begin(), this->m_xs.end()));
      const ::std::size_t n = this->m_xs.size();
      this->m_xs.resize(this->capacity() + 1);
      ::std::iota(this->m_xs.begin() + n, this->m_xs.end(), this->m_xs[n - 1] + 1);
    }

    li_chao_segtree() = default;
    li_chao_segtree(const ::tools::li_chao_segtree<T>&) = default;
    li_chao_segtree(::tools::li_chao_segtree<T>&&) = default;
    ~li_chao_segtree() = default;
    ::tools::li_chao_segtree<T>& operator=(const ::tools::li_chao_segtree<T>&) = default;
    ::tools::li_chao_segtree<T>& operator=(::tools::li_chao_segtree<T>&&) = default;

    void add(const T& a, const T& b) {
      if (this->m_xs.empty()) return;

      this->add_impl(a, b, 1);
    }

    void add(const T& a, const T& b, const T& l, const T& r) {
      if (this->m_xs.empty()) return;

      auto l_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), l);
      auto r_id = ::tools::lower_bound(this->m_xs.begin(), ::std::prev(this->m_xs.end()), r);
      if (r_id == ::std::ssize(this->m_xs) - 1 || r < this->m_xs[r_id]) --r_id;
      if (r_id < l_id) return;
      l_id += this->capacity();
      r_id += this->capacity() + 1;

      for (; l_id < r_id; l_id >>= 1, r_id >>= 1) {
        if (l_id & 1) {
          this->add_impl(a, b, l_id);
          ++l_id;
        }
        if (r_id & 1) {
          --r_id;
          this->add_impl(a, b, r_id);
        }
      }
    }

    T query(const T& x) const {
      const auto it = ::std::lower_bound(this->m_xs.begin(), this->m_xs.end(), x);
      assert(*it == x);
      const ::std::size_t node_id = this->capacity() + ::std::distance(this->m_xs.begin(), it);

      T answer = this->m_maximal ? ::std::numeric_limits<T>::min() : ::std::numeric_limits<T>::max();
      for (::std::size_t h = this->m_height + 1; h --> 0;) {
        const auto& [fa, fb] = this->m_nodes[node_id >> h];
        if (this->comp(answer, fa * x + fb)) {
          answer = fa * x + fb;
        }
      }
      
      return answer;
    }
  };
}


#line 8 "tests/li_chao_segtree/line.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  ll N, Q;
  std::cin >> N >> Q;
  std::vector<ll> a(N), b(N);
  for (ll i = 0; i < N; ++i) {
    std::cin >> a[i] >> b[i];
  }
  std::vector<std::tuple<ll, ll, ll>> queries(Q);
  for (ll i = 0; i < Q; ++i) {
    std::cin >> std::get<0>(queries[i]);
    if (std::get<0>(queries[i]) == 0) {
      std::cin >> std::get<1>(queries[i]) >> std::get<2>(queries[i]);
    } else {
      std::cin >> std::get<1>(queries[i]);
    }
  }

  std::vector<ll> x;
  for (const auto& [t, p, _] : queries) {
    if (t == 1) {
      x.push_back(p);
    }
  }
  std::sort(x.begin(), x.end());
  x.erase(std::unique(x.begin(), x.end()), x.end());
  tools::li_chao_segtree<ll> seg(x.begin(), x.end(), false);

  for (ll i = 0; i < N; ++i) {
    seg.add(a[i], b[i]);
  }
  for (const auto& [t, q1, q2] : queries) {
    if (t == 0) {
      seg.add(q1, q2);
    } else {
      std::cout << seg.query(q1) << '\n';
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	half_00	AC	59 ms	13 MB
g++	hand_max_00	AC	183 ms	25 MB
g++	max_random_00	AC	107 ms	18 MB
g++	max_random_01	AC	113 ms	18 MB
g++	max_random_02	AC	110 ms	18 MB
g++	no_output_00	AC	76 ms	11 MB
g++	parabola_random_00	AC	154 ms	18 MB
g++	parabola_random_01	AC	159 ms	18 MB
g++	parabola_random_02	AC	157 ms	18 MB
g++	random_00	AC	82 ms	15 MB
g++	random_01	AC	82 ms	15 MB
g++	random_02	AC	53 ms	11 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB