#line 1 "test/aoj/DSL_2_F/main.dynamic.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_F"
#include <climits>
#include <iostream>
#line 2 "Mylib/AlgebraicStructure/Monoid/min.cpp"
#include <algorithm>
#include <optional>
namespace haar_lib {
template <typename T>
struct min_monoid {
using value_type = std::optional<T>;
value_type operator()() const { return {}; }
value_type operator()(const value_type &a, const value_type &b) const {
if (not a) return b;
if (not b) return a;
return {std::min(*a, *b)};
}
};
} // namespace haar_lib
#line 3 "Mylib/AlgebraicStructure/Monoid/update.cpp"
namespace haar_lib {
template <typename T>
struct update_monoid {
using value_type = std::optional<T>;
value_type operator()() const { return std::nullopt; }
value_type operator()(const value_type &a, const value_type &b) const { return (a ? a : b); }
};
} // namespace haar_lib
#line 2 "Mylib/AlgebraicStructure/MonoidAction/update_min.cpp"
namespace haar_lib {
template <typename MonoidUpdate, typename MonoidGet>
struct update_min {
using monoid_get = MonoidGet;
using monoid_update = MonoidUpdate;
using value_type_get = typename MonoidGet::value_type;
using value_type_update = typename MonoidUpdate::value_type;
value_type_get operator()(value_type_get a, value_type_update b, int) const {
return b ? *b : a;
}
};
} // namespace haar_lib
#line 2 "Mylib/DataStructure/SegmentTree/dynamic_lazy_segment_tree.cpp"
#include <cstdint>
namespace haar_lib {
template <typename Monoid>
class dynamic_lazy_segment_tree {
public:
using monoid_get = typename Monoid::monoid_get;
using monoid_update = typename Monoid::monoid_update;
using value_type_get = typename monoid_get::value_type;
using value_type_update = typename monoid_update::value_type;
private:
struct node {
value_type_get value;
value_type_update lazy;
node *left = nullptr, *right = nullptr;
node() {}
node(const value_type_get &value, const value_type_update &lazy) : value(value), lazy(lazy) {}
};
Monoid M_;
monoid_get M_get_;
monoid_update M_update_;
int64_t depth_, size_, hsize_;
node *root_ = nullptr;
void propagate(node *t, int64_t l, int64_t r) {
if (t->lazy == M_update_()) return;
if (r - l > 1) {
if (not t->left) t->left = new node(M_get_(), M_update_());
t->left->lazy = M_update_(t->lazy, t->left->lazy);
if (not t->right) t->right = new node(M_get_(), M_update_());
t->right->lazy = M_update_(t->lazy, t->right->lazy);
}
const int64_t len = r - l;
t->value = M_(t->value, t->lazy, len);
t->lazy = M_update_();
}
node *update(node *t, int64_t l, int64_t r, int64_t x, int64_t y, value_type_update value) {
if (not t) t = new node(M_get_(), M_update_());
propagate(t, l, r);
if (r - l == 1) {
if (x <= l and r <= y) t->lazy = M_update_(value, t->lazy);
propagate(t, l, r);
return t;
}
if (r < x or y < l) return t;
if (x <= l and r <= y) {
t->lazy = M_update_(value, t->lazy);
propagate(t, l, r);
return t;
}
t->left = update(t->left, l, (l + r) / 2, x, y, value);
t->right = update(t->right, (l + r) / 2, r, x, y, value);
t->value = M_get_(t->left->value, t->right->value);
return t;
}
value_type_get get(node *t, int64_t l, int64_t r, int64_t x, int64_t y) {
if (not t) return M_get_();
propagate(t, l, r);
if (r <= x or y <= l) return M_get_();
if (x <= l and r <= y) return t->value;
return M_get_(
get(t->left, l, (l + r) / 2, x, y),
get(t->right, (l + r) / 2, r, x, y));
}
public:
dynamic_lazy_segment_tree() {}
dynamic_lazy_segment_tree(int64_t n) : depth_(n > 1 ? 64 - __builtin_clzll(n - 1) + 1 : 1),
size_(1LL << depth_),
hsize_(size_ / 2) {
root_ = new node(M_get_(), M_update_());
}
void update(int64_t l, int64_t r, value_type_update value) {
update(root_, 0, hsize_, l, r, value);
}
value_type_get fold(int64_t l, int64_t r) {
return get(root_, 0, hsize_, l, r);
}
value_type_get operator[](int64_t i) {
return fold(i, i + 1);
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#include <utility>
#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 10 "test/aoj/DSL_2_F/main.dynamic.test.cpp"
namespace hl = haar_lib;
using update = hl::update_monoid<int>;
using min = hl::min_monoid<int>;
int main() {
int n, q;
std::cin >> n >> q;
hl::dynamic_lazy_segment_tree<hl::update_min<update, min>> seg(n);
for (auto [type, s, t] : hl::input_tuples<int, int, int>(q)) {
if (type == 0) {
int x;
std::cin >> x;
seg.update(s, t + 1, x);
} else {
std::cout << seg.fold(s, t + 1).value_or(INT_MAX) << std::endl;
}
}
return 0;
}
test/aoj/DSL_2_F/main.dynamic.test.cpp
Min monoid
(Mylib/AlgebraicStructure/Monoid/min.cpp)