Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void buildTree(vector<long long>& tree, vector<long long>& arr, long long node, long long l, long long r){
    if (l==r){
        tree[node]=arr[l];
        return;
    }

    long long mid=(l+r)/2;

    buildTree(tree, arr, node*2, l, mid);
    buildTree(tree, arr, node*2+1, mid+1, r);

    tree[node]=min(tree[node*2], tree[node*2+1]);
}

void update(vector<long long>& tree, long long pos, long long val, long long node, long long l, long long r){
    if (l==r){
        tree[node]=val;
        return;
    } 

    long long mid=(l+r)/2;

    if (pos<=mid){
        update(tree, pos, val, node*2, l, mid);
    } else {
        update(tree, pos, val, node*2+1, mid+1, r);
    }

    tree[node]=min(tree[2*node], tree[2*node+1]);
}

long long query(vector<long long>& tree, long long ql, long long qr, long long node, long long l, long long r){
    if (qr<l || ql>r){
        return INT_MAX;
    }
    if (ql<=l && qr>=r){
        return tree[node];
    }

    long long mid=(l+r)/2;

    return min(query(tree, ql, qr, node*2, l, mid), query(tree, ql, qr, node*2+1, mid+1, r));
}

int main(){
    long long n, q;
    cin >> n >> q;
    vector<long long> arr(n+1);
    for (long long i=0;i<n;i++){
        cin >> arr[i+1];
    }

    vector<vector<long long>> queries(q, vector<long long>(3));
    for (long long i=0;i<q;i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    vector<long long> segTree(4*n);
    buildTree(segTree, arr, 1, 1, n);


    for (auto &q: queries){
        if (q[0]==1){
            update(segTree, q[1], q[2], 1, 1, n);
        } else if (q[0]==2){
            cout << query(segTree, q[1], q[2], 1, 1, n) << '\n';
        }
    }
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED