【題解】CSES 1649 Dynamic Range Minimum Queries

#include <bits/stdc++.h>
using namespace std;
 
int n, q, mn[200005*4];
 
void update(int x, int l, int r, int ux, int u){
    if (l == r){
        mn[x] = u;
        return;
    }
    int mid = (l+r)/2;
    if (ux <= mid) update(x*2, l, mid, ux, u);
    else update(x*2+1, mid+1, r, ux, u);
    mn[x] = min(mn[x*2], mn[x*2+1]);
}
 
int query(int x, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr) return mn[x];
    int mid = (l+r)/2;
    int ret = 1000000000;
    if (ql <= mid) ret = min(ret, query(x*2, l, mid, ql, qr));
    if (mid < qr) ret = min(ret, query(x*2+1, mid+1, r, ql, qr));
    return ret;
}
 
int main(){
    cin >> n >> q;
    for (int i = 1, a; i <= n; i++){
        cin >> a;
        update(1, 1, n, i, a);
    }
    for (int i = 0, type, a, b; i < q; i++){
        cin >> type >> a >> b;
        if (type == 1){
            update(1, 1, n, a, b);
        }
        else{
            cout << query(1, 1, n, a, b) << "\n";
        }
    }
}