dynamic_range_minimum_queries_1649.cpp (1117B)
1 #include <algorithm> 2 #include <iostream> 3 #include <vector> 4 5 constexpr size_t inf = 1999999999; 6 7 class SegmentTree { 8 public: 9 SegmentTree(size_t n) : m{pow2ceil(n)}, v(2*m, inf) {} 10 11 void update(size_t i, size_t x) { 12 v[m+i-1] = x; 13 for (size_t p = (m+i-1)/2; p > 0; p /= 2) 14 v[p] = std::min(v[2*p], v[2*p+1]); 15 } 16 17 size_t min(size_t a, size_t b) { return q(a-1, b, 1, 0, m); } 18 19 private: 20 size_t m; 21 std::vector<size_t> v; 22 static constexpr size_t pow2ceil(size_t x) { 23 size_t c; 24 for (c = 1; c < x; c *= 2) ; 25 return c; 26 } 27 28 size_t q(size_t a, size_t b, size_t i, size_t l, size_t r) { 29 if (a == l && b == r) return v[i]; 30 size_t p{(l+r)/2}, s{inf}; 31 if (a < p) s = std::min(s, q(a, std::min(b, p), 2*i, l, p)); 32 if (b > p) s = std::min(s, q(std::max(a, p), b, 2*i+1, p, r)); 33 return s; 34 } 35 }; 36 37 int main() { 38 size_t n, q; 39 std::cin >> n >> q; 40 SegmentTree t(n); 41 for (size_t i = 0; i < n; i++) { 42 size_t x; 43 std::cin >> x; 44 t.update(i+1, x); 45 } 46 for (size_t i = 0; i < q; i++) { 47 int u, a, b; 48 std::cin >> u >> a >> b; 49 if (u == 1) 50 t.update(a, b); 51 else 52 std::cout << t.min(a, b) << "\n"; 53 } 54 }