Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;

template<class T, class Op>
struct SegTree {
    int n;
    T ID;
    Op op;
    vector<T> st;

    SegTree(int n = 0, T ID = T(), Op op = Op()) { init(n, ID, op); }

    void init(int n_, T ID_, Op op_ = Op()) {
        n = n_;
        ID = ID_;
        op = op_;
        st.assign(2 * n, ID);
    }

    void build(const vector<T> &a) {
        n = (int) a.size();
        st.assign(2 * n, ID);
        for (int i = 0; i < n; i++) st[n + i] = a[i];
        for (int i = n - 1; i > 0; i--) st[i] = op(st[i << 1], st[i << 1 | 1]);
    }

    void set(int i, T v) {
        for (st[i += n] = v; i > 1; i >>= 1)
            st[i >> 1] = op(st[i], st[i ^ 1]);
    }

    T query(int l, int r) const {
        T resL = ID, resR = ID;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resL = op(resL, st[l++]);
            if (r & 1) resR = op(st[--r], resR);
        }
        return op(resL, resR);
    }
};

struct MinOp {
    long long operator()(long long a, long long b) const {
        return min(a, b);
    }
};

const long long MIN_ID = LLONG_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n, q;
    cin >> n >> q;
    vector<long long> origValues(n);
    for (int i = 0; i < n; i++) {
        cin >> origValues[i];
    }
    auto tree = SegTree(n, MIN_ID, MinOp());
    tree.build(origValues);
    for (int i = 0; i < q; i++) {
        int oper, a, b;
        cin >> oper >> a >> b;
        if (oper == 1) {
            tree.set(a-1, b);
        } else {
            cout << tree.query(a-1, b-1) << endl;
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED