Dynamic Range Minimum Queries

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

const int NMX = 524288;
ll ar[NMX];

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

ll find_min(int a, int b) {
	ll m = LLONG_MAX;
	while (a <= b) {
		if (a%2 == 1) {
			m = min(m, ar[a]);
			a++;
		}
		if (b%2 == 0) {
			m = min(m, ar[b]);
			b--;
		}
		a /= 2;
		b /= 2;
	}
	return m;
}

int main() {
	int n, q;
	cin >> n >> q;
	int p = 1;
	while (p < n) p*=2;
	
	for (int i=p; i<2*p; i++) {
		ar[i] = LLONG_MAX;
	}
	for (int i=0; i<n; i++) {
		int b;
		cin >> b;
		update(i+p, b);
	}
	vector<ll> outs;
	outs.reserve(q);
	for (int i=0; i<q; i++) {
		int c;
		ll a, b;
		cin >> c >> a >> b;
		if (c == 1) update(a+p-1, b);
		if (c == 2) outs.push_back(find_min(a+p-1, b+p-1));
	}
	for (auto i : outs) {
		cout << i << endl;
	}
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED