#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A"
#include <iostream>
#include "examples/cpp/segment_tree.hpp"
#include "examples/cpp/macros.hpp"
using namespace std;
int main() {
int n, q; cin >> n >> q;
min_segment_tree segtree(n);
REP (i, n) {
segtree.point_set(i, (1u << 31) - 1);
}
REP (i, q) {
int com, x, y; cin >> com >> x >> y;
if (com == 0) {
segtree.point_set(x, y);
} else if (com == 1) {
cout << segtree.range_concat(x, y + 1) << endl;
}
}
return 0;
}
#line 1 "examples/cpp/segment_tree_tests/segment_tree.range_minimum_query.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_A"
#include <iostream>
#line 2 "examples/cpp/segment_tree.hpp"
#include <cassert>
#include <vector>
#line 2 "examples/cpp/monoids.hpp"
#include <algorithm>
#include <cstdint>
struct plus_monoid {
typedef int64_t value_type;
value_type unit() const { return 0; }
value_type mult(value_type a, value_type b) const { return a + b; }
};
struct max_monoid {
typedef int64_t value_type;
value_type unit() const { return INT64_MIN; }
value_type mult(value_type a, value_type b) const { return std::max(a, b); }
};
struct min_monoid {
typedef int64_t value_type;
value_type unit() const { return INT64_MAX; }
value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};
#line 5 "examples/cpp/segment_tree.hpp"
/**
* @brief a Segment Tree (generalized with monoids)
* @tparam Monoid is a monoid; commutativity is not required
* @see https://en.wikipedia.org/wiki/Segment_tree
*/
template <class Monoid>
struct segment_tree {
typedef typename Monoid::value_type value_type;
const Monoid mon;
int n;
std::vector<value_type> a;
segment_tree() = default;
segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
n = 1; while (n < n_) n *= 2;
a.resize(2 * n - 1, mon.unit());
}
/**
* @brief set $a_i$ as b in $O(\log n)$
* @arg i is 0-based
*/
void point_set(int i, value_type b) {
assert (0 <= i and i < n);
a[i + n - 1] = b;
for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
}
}
/**
* @brief compute $a_l \cdot a _ {l + 1} \cdot ... \cdot a _ {r - 1}$ in $O(\log n)$
* @arg l, r are 0-based
*/
value_type range_concat(int l, int r) {
assert (0 <= l and l <= r and r <= n);
value_type lacc = mon.unit(), racc = mon.unit();
for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
}
return mon.mult(lacc, racc);
}
};
typedef segment_tree<plus_monoid> plus_segment_tree;
typedef segment_tree<max_monoid> max_segment_tree;
typedef segment_tree<min_monoid> min_segment_tree;
#line 1 "examples/cpp/macros.hpp"
// for 文用マクロ
#line 4 "examples/cpp/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#line 5 "examples/cpp/segment_tree_tests/segment_tree.range_minimum_query.cpp"
using namespace std;
int main() {
int n, q; cin >> n >> q;
min_segment_tree segtree(n);
REP (i, n) {
segtree.point_set(i, (1u << 31) - 1);
}
REP (i, q) {
int com, x, y; cin >> com >> x >> y;
if (com == 0) {
segtree.point_set(x, y);
} else if (com == 1) {
cout << segtree.range_concat(x, y + 1) << endl;
}
}
return 0;
}
examples/cpp/segment_tree_tests/segment_tree.range_minimum_query.cpp