Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <utility>

using namespace std;
#define BIG 9999999999

void update(int k, long v, int n, vector<long> &d) {
    k += n;
    d[k] = v;
    for (k /= 2; k >= 1; k/=2) {
        d[k] = min(d[2*k], d[2*k+1]);
    }
}

long get(int a, int b, int n, vector<long> &d) {
    a += n; b += n;
    long m = BIG;
    while (a <= b) {
        if (a%2 == 1) m = min(m, d[a++]);
        if (b%2 == 0) m = min(m, d[b--]);
        a /= 2; b /= 2;
    }
    return m;
}

int main(){
    int n, q;
    cin >> n >> q;
    long long tmax = 1;
    while (tmax < n * 2) {
        tmax <<= 1;
    }
    vector<long> d(tmax, BIG);
    for (int i = 0; i < n; ++i) {
        long v;
        cin >> v;
        update(i, v, n, d);
    }
    vector<vector<int>> qs(q, vector<int>(3));
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> qs[i][j];
        }
    }
    for (auto q : qs) {
        if (q[0] == 1) {
            update(q[1] -1, q[2], n, d);

        } else {
            cout << get(q[1] -1, q[2] -1, n, d) << endl;
        }
    }
    
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED