Dynamic Range Minimum Queries

input/code.cpp: In function 'int main()':
input/code.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   51 |     for(int i=0; i < nc; i++) {
      |                  ~~^~~~
input/code.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   52 |         if(i < n) cin >> ar[i];
      |            ~~^~~
input/code.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   58 |     for(int i=0; i<q; i++) {
      |                  ~^~

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

const unsigned int N = 2e5;
const unsigned int N2 = bit_ceil(N);
int ar[N2+1];
int tree[2*N2+1];

void bfs(int k, int qi, int qe) {
    if(qe-qi <= 1) tree[k] = ar[qi];
    else {
        int a=2*k;
        int b=a+1;
        int mid = (qe+qi)/2;
        bfs(a, qi, mid);
        bfs(b, mid, qe);
        tree[k]=min(tree[a], tree[b]);
    }
}

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

int getMin(int a, int b) {
    int res = INT_MAX;

    while (a<b) {
        if(a % 2) {
            res = min(res, tree[a]);
            a++;
        };
        if(b % 2) {
            b--;
            res = min(res, tree[b]);
        };
        a /= 2; b /= 2;
    }
    return res;
}

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

    unsigned int nc = bit_ceil(n);


    for(int i=0; i < nc; i++) {
        if(i < n) cin >> ar[i];
        else ar[i] = INT_MAX;
    }

    bfs(1, 0, nc);

    for(int i=0; i<q; i++) {
        int o, a, b;
        cin >> o >> a >> b;
        if(o == 1) update(nc+a-1, b);
        if(o == 2) cout << getMin(nc+a-1, nc+b) << '\n';
    }


    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED