Dynamic Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;

int n;
vector<int> tree;

int minq(int a, int b) {
    a += n; b += n;
    int m = numeric_limits<int>::max();
    while (a <= b) {
        if (a%2 == 1) m = min(m,tree[a++]);
        if (b%2 == 0) m = min(m,tree[b--]);
        a /= 2; b /= 2;
    }
    return m;
}

void update(int k, int x) {
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k],tree[2*k+1]);
    }
}

int main() {
    int q;
    cin >> n >> q;
    tree.resize(2*n);

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        update(i, x);
    }

    int queries[q][3];
    for (int i = 0; i < q; i++)
    {
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }
    
    for (auto &&quer : queries)
    {
        if (quer[0] == 1) update(quer[1]-1, quer[2]);
        else cout << minq(quer[1]-1, quer[2]-1) << endl;
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED