Dynamic Range Minimum Queries

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

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

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<long long> tree(4 * n + 5);

    for (int i = 1; i <= n; ++i) {
        tree[n + i - 1] = a[i];
    }

    for (int i = n - 1; i >= 1; --i) {
        tree[i] = min(tree[2 * i], tree[2 * i + 1]);
    }


    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int k;
            long long u;
            cin >> k >> u;

            int pos = n + k - 1;
            tree[pos] = u;

            for (pos /= 2; pos >= 1; pos /= 2) {
                tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
            }
        } else {
            int L, R;
            cin >> L >> R;

            long long ans = LLONG_MAX;

            L += n - 1;
            R += n - 1;

            while (L <= R) {
                if (L % 2 == 1) {
                    ans = min(ans, tree[L]);
                    ++L;
                }
                if (R % 2 == 0) {
                    ans = min(ans, tree[R]);
                    --R;
                }
                L /= 2;
                R /= 2;
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED