#line 1 "test/yosupo-judge/line_add_get_min/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#include <iostream>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>
#line 2 "Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp"
#include <algorithm>
#include <optional>
#line 6 "Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp"
namespace haar_lib {
template <typename T, typename Comparator>
class lichao_segment_tree {
public:
using value_type = T;
private:
using line = std::pair<T, T>;
Comparator cmp_ = Comparator();
std::vector<T> xs_;
int n_;
std::vector<std::optional<line>> data_;
std::vector<std::pair<int, int>> range_;
T chm(const T &a, const T &b) const {
return cmp_(a, b) ? a : b;
}
void init_range_(int i, int left, int right) {
if (i >= 2 * n_) return;
range_[i] = std::make_pair(left, right);
const int mid = (left + right) / 2;
init_range_(i << 1 | 0, left, mid);
init_range_(i << 1 | 1, mid, right);
}
public:
lichao_segment_tree() {}
lichao_segment_tree(std::vector<T> xs) : xs_(xs) {
std::sort(xs_.begin(), xs_.end());
xs_.erase(std::unique(xs_.begin(), xs_.end()), xs_.end());
n_ = 1;
while (n_ < (int) xs_.size()) n_ *= 2;
const auto m = xs_.back();
xs_.resize(n_, m);
data_.assign(2 * n_, std::nullopt);
range_.resize(2 * n_);
init_range_(1, 0, n_);
}
T apply(const line &l, const T &x) const {
return l.first * x + l.second;
}
private:
void update(int i, line new_line, int l, int r) {
if (not data_[i]) {
data_[i] = new_line;
return;
}
const int m = (l + r) / 2;
auto lx = xs_[l], mx = xs_[m], rx = xs_[r - 1];
bool left = cmp_(apply(new_line, lx), apply(*data_[i], lx));
bool mid = cmp_(apply(new_line, mx), apply(*data_[i], mx));
bool right = cmp_(apply(new_line, rx), apply(*data_[i], rx));
if (left and right) {
data_[i] = new_line;
return;
}
if (not left and not right) {
return;
}
if (mid) {
std::swap(*data_[i], new_line);
}
if (left != mid) {
update(i << 1 | 0, new_line, l, m);
} else {
update(i << 1 | 1, new_line, m, r);
}
}
public:
void add_line(T a, T b) {
update(1, std::make_pair(a, b), 0, n_);
}
// [l, r)
void add_segment(T l, T r, T a, T b) {
int left = std::lower_bound(xs_.begin(), xs_.end(), l) - xs_.begin();
int right = std::lower_bound(xs_.begin(), xs_.end(), r) - xs_.begin();
int L = left + n_;
int R = right + n_;
while (L < R) {
if (R & 1) {
--R;
update(R, std::make_pair(a, b), range_[R].first, range_[R].second);
}
if (L & 1) {
update(L, std::make_pair(a, b), range_[L].first, range_[L].second);
++L;
}
L >>= 1;
R >>= 1;
}
}
public:
auto operator()(const T &x) const {
const int i = std::lower_bound(xs_.begin(), xs_.end(), x) - xs_.begin();
int k = i + n_;
std::optional<T> ret;
while (k > 0) {
if (data_[k]) {
if (not ret)
ret = apply(*data_[k], xs_[i]);
else
ret = chm(*ret, apply(*data_[k], xs_[i]));
}
k >>= 1;
}
return ret;
}
};
template <typename T>
auto make_lichao_min(const std::vector<T> &xs) {
return lichao_segment_tree<T, std::less<T>>(xs);
}
template <typename T>
auto make_lichao_max(const std::vector<T> &xs) {
return lichao_segment_tree<T, std::greater<T>>(xs);
}
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#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 10 "test/yosupo-judge/line_add_get_min/main.test.cpp"
namespace hl = haar_lib;
using Query = std::variant<std::pair<int64_t, int64_t>, int64_t>;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
std::vector<int64_t> xs;
std::vector<std::pair<int64_t, int64_t>> lines;
for (auto [a, b] : hl::input_tuples<int64_t, int64_t>(N)) {
lines.emplace_back(a, b);
}
std::vector<Query> query;
for (auto [type] : hl::input_tuples<int>(Q)) {
switch (type) {
case 0: {
int64_t a, b;
std::cin >> a >> b;
query.push_back(std::make_pair(a, b));
break;
}
case 1: {
int64_t p;
std::cin >> p;
query.push_back(p);
xs.push_back(p);
break;
}
}
}
auto lc = hl::make_lichao_min(xs);
for (auto [a, b] : lines) {
lc.add_line(a, b);
}
for (auto &q : query) {
if (q.index() == 0) {
auto [a, b] = std::get<0>(q);
lc.add_line(a, b);
} else {
auto p = std::get<1>(q);
auto res = lc(p);
std::cout << *res << "\n";
}
}
return 0;
}
test/yosupo-judge/line_add_get_min/main.test.cpp
Input tuple
(Mylib/IO/input_tuple.cpp)