Dynamic Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;
#define int long long

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

int n,q;
const int maxN = 2e5;
const int tree_size = maxN*4;

vector<int> tree;
vector<int> values;

void build(int node, int start, int end) {

    // leaf node
    if (start == end) {
        tree[node] = values[start];
    } 
    // internal nodes
    else {
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid); // left child
        build(2 * node + 2, mid + 1, end); // right child
        tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
    }
}

void update(int node, int start, int end, int idx, int val) {

    // leaf node
    if (start == end) {
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node + 1, start, mid, idx, val); // left child
        } else {
            update(2 * node + 2, mid + 1, end, idx, val); // right child
        }
        tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
    }
}



int query(int node, int start, int end, int left, int right) {

    if (right < start || end < left) {
        return INT_MAX;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }

    int mid = (start + end) / 2;
    int left_min = query(2 * node + 1, start, mid, left, right);
    int right_min = query(2 * node + 2, mid + 1, end, left, right);
    return min(left_min, right_min);
}



signed main() {

    cin >> n >> q;

    vector<int> results;
    tree.resize(n*4, 0);


    // build Segment tree
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        values.push_back(x);
    }
    build(0,0,n-1);

    // handle queries
    for (int i = 0; i < q; i++) {
        int type, a, b;
        cin >> type >> a >> b;

        if (type == 1) {
            update(0, 0, n - 1, a - 1, b); // fix index
        } else if (type == 2) {
            int res = query(0, 0, n - 1, a - 1, b - 1); // fix index
            results.push_back(res);
        }
    }

    for (int r : results) {
        cout << r << "\n";
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED