Dynamic Range Minimum Queries

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

typedef long long ll;


int main() {
    ll n, q;
    cin >> n;
    cin >> q;

    
    ll val[2*n] = {0};
    for(ll i = 0; i < n; i++) {
        cin >> val[n+i];
    }

    
    for(ll i = 0; i<n-1; i++) {
        val[n-i-1] = min(val[2*n - i*2 -2],val[2*n - i*2 -1]);
    }

    // for(ll i = 0; i < 2*n; i++) {
    //     cout << val[i] << " ";
    // }
    // cout << endl;


    ll a,b,k,u;
    ll tmp;

    ll result[q];
    ll result_id = 0;
    
    for(ll q_id = 0; q_id < q; q_id++){
        cin >> tmp;
        if(tmp == 1) {
            cin >> k;
            cin >> u;

            k += n-1;
            val[k] = u;
            for (k /= 2; k >= 1; k /= 2) {
                val[k] = min(val[2*k],val[2*k+1]);
            }

        } else {
            cin >> a;
            cin >> b;

            a += n-1; b += n-1;
            ll s = 10000000000;
            while (a <= b) {
                if (a%2 == 1) s = min(s,val[a++]);
                if (b%2 == 0) s = min(s,val[b--]);
                a /= 2; b /= 2;
            }

            result[result_id] = s;
            result_id++;
        }
    }

    for(ll i = 0; i < result_id; i++) {
        cout << result[i] << endl;
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED