#line 1 "test/yosupo-judge/line_add_get_min/main.dynamic.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#include <climits>
#include <iostream>
#line 2 "Mylib/DataStructure/ConvexHullTrick/dynamic_lichao_segment_tree.cpp"
#include <optional>
#include <utility>
namespace haar_lib {
template <typename T, typename Comparator>
class dynamic_lichao_segment_tree {
public:
using value_type = T;
private:
using line = std::pair<T, T>;
struct node {
std::optional<line> value;
int64_t l, r;
node *l_child = nullptr, *r_child = nullptr;
node(std::optional<line> value, int64_t l, int64_t r) : value(value), l(l), r(r) {}
};
Comparator cmp_ = Comparator();
int64_t MIN_, MAX_;
node *root_ = nullptr;
T chm(const T &a, const T &b) const {
return cmp_(a, b) ? a : b;
}
public:
dynamic_lichao_segment_tree() {}
dynamic_lichao_segment_tree(int64_t MIN, int64_t MAX) : MIN_(MIN), MAX_(MAX) {}
T apply(const line &l, const T &x) const {
return l.first * x + l.second;
}
private:
node *update(node *t, line new_line, int64_t l, int64_t r) {
if (not t) {
return t = new node(new_line, l, r);
}
if (not t->value) {
t->value = new_line;
return t;
}
if (l + 1 == r) {
if (cmp_(apply(new_line, l), apply(*(t->value), l))) {
t->value = new_line;
}
return t;
}
const auto m = (l + r) / 2;
bool left = cmp_(apply(new_line, l), apply(*(t->value), l));
bool mid = cmp_(apply(new_line, m), apply(*(t->value), m));
bool right = cmp_(apply(new_line, r), apply(*(t->value), r));
if (left and right) {
t->value = new_line;
return t;
}
if (not left and not right) {
return t;
}
if (mid) {
std::swap(*(t->value), new_line);
}
if (left != mid) {
t->l_child = update(t->l_child, new_line, l, m);
} else {
t->r_child = update(t->r_child, new_line, m, r);
}
return t;
}
node *update_segment(node *t, line new_line, int64_t l, int64_t r, int64_t sl, int64_t sr) {
if (r < sl or sr < l) return t;
if (sl <= l and r <= sr) {
return t = update(t, new_line, l, r);
}
if (l + 1 == r) {
return t;
}
if (not t)
t = new node(std::nullopt, l, r);
else {
if (t->value) {
if (
cmp_(apply(*(t->value), l), apply(new_line, l)) and
cmp_(apply(*(t->value), r), apply(new_line, r))) {
return t;
}
}
}
const auto m = (l + r) / 2;
t->l_child = update_segment(t->l_child, new_line, l, m, sl, sr);
t->r_child = update_segment(t->r_child, new_line, m, r, sl, sr);
return t;
}
public:
void add_line(T a, T b) {
root_ = update(root_, std::make_pair(a, b), MIN_, MAX_);
}
void add_segment(int64_t l, int64_t r, T a, T b) {
root_ = update_segment(root_, std::make_pair(a, b), MIN_, MAX_, l, r);
}
auto operator()(const int64_t &x) const {
std::optional<T> ret;
node *cur = root_;
while (cur) {
if (cur->value) {
if (not ret)
ret = apply(*(cur->value), x);
else
ret = chm(*ret, apply(*(cur->value), x));
}
const auto m = (cur->l + cur->r) / 2;
if (x < m)
cur = cur->l_child;
else
cur = cur->r_child;
}
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#line 6 "Mylib/IO/input_tuples.cpp"
#include <vector>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 7 "test/yosupo-judge/line_add_get_min/main.dynamic.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
auto lc = hl::dynamic_lichao_segment_tree<int64_t, std::less<>>(INT_MIN, INT_MAX);
for (auto [a, b] : hl::input_tuples<int64_t, int64_t>(N)) {
lc.add_line(a, b);
}
for (auto [type] : hl::input_tuples<int>(Q)) {
if (type == 0) {
int64_t a, b;
std::cin >> a >> b;
lc.add_line(a, b);
} else {
int64_t p;
std::cin >> p;
std::cout << *lc(p) << "\n";
}
}
return 0;
}
test/yosupo-judge/line_add_get_min/main.dynamic.test.cpp
Input tuple
(Mylib/IO/input_tuple.cpp)