Dynamic Range Minimum Queries

input/code.cpp: In function 'void build(long long int, long long int, long long int)':
input/code.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int m = lx + rx >> 1;
      |             ~~~^~~~
input/code.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
input/code.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int m = lx + rx >> 1;
      |             ~~~^~~~
input/code.cpp: In function 'long long int que(long long int, long long int, long long int, long long int, long long int)':
input/code.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int m = lx + rx >> 1;
      |             ~~~^~~~

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

const int N = 2e5 + 5;
const int INF = 1e9;

int n, q;
int a[N];

int nd[N << 2];

void build(int x, int lx, int rx) {
    if (lx == rx) {
        nd[x] = a[lx];
        return;
    }
    int m = lx + rx >> 1;
    build(x << 1, lx, m);
    build(x << 1 | 1, m + 1, rx);
    nd[x] = min(nd[x << 1], nd[x << 1 | 1]);
}

void upd(int i, int v, int x, int lx, int rx) {
    if (lx == rx) {
        nd[x] = v;
        return;
    }
    int m = lx + rx >> 1;
    if (i <= m) upd(i, v, x << 1, lx, m);
    else upd(i, v, x << 1 | 1, m + 1, rx);
    nd[x] = min(nd[x << 1], nd[x << 1 | 1]);
}

int que(int l, int r, int x, int lx, int rx) {
    if (lx > r || rx < l) return INF;
    if (l <= lx && rx <= r) return nd[x];
    int m = lx + rx >> 1;
    return min(que(l, r, x << 1, lx, m), que(l, r, x << 1 | 1, m + 1, rx));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    build(1, 1, n);
    while (q--) {
        int tt;
        cin >> tt;
        if (tt == 1) {
            int k, u;
            cin >> k >> u;
            upd(k, u, 1, 1, n);
        } else {
            int l, r;
            cin >> l >> r;
            cout << que(l, r, 1, 1, n) << '\n';
        }
    }    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED