Dynamic Range Minimum Queries

#include <bits/stdc++.h>
using namespace std;

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);                             // never mix with scanf/printf after this
    // int n; cin >> n; 
    int n,q; cin >> n >> q; 
    vi t(2 * n);                                                // t[n..2n-1]  leaves, t[1] = root, t[0] unused
    for (int i = 0; i < n; i++) cin >> t[n + i];
    for (int i = n - 1; i >= 1; i--) t[i] = min(t[2*i], t[2*i+1]);

    while (q--) {
        int type, x, y; cin >> type >> x >> y;
        if (type == 1) {                                        // point update: position x -> value y
            int p = n + (x - 1);
            t[p] = y;
            for (p >>= 1; p >= 1; p >>= 1) t[p] = min(t[2*p], t[2*p+1]);
        } else {                                                // min on [x, y] 1-indexed -> [x-1, y) 0-indexed
            int res = INT_MAX;
            for (int l = n + x - 1, r = n + y; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = min(res, t[l++]);
                if (r & 1) res = min(res, t[--r]);
            }
            cout << res << '\n';
        }
    }
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED