Dynamic Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,c,d) for (int i = c; i < d; i++)

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);

	//Input definition
	int n;
	int q;

	cin >> n >> q;

	//Define segment tree
	ll seg[2*n];
	seg[0] = -1;

	//Read in values
	REP(i,0,n){
		cin >> seg[i+n];
	}
	
	//Build segmentation tree
	for(int i=n-1;i>0;i--){
		seg[i] = min(seg[2*i], seg[(2*i)+1]);
	}

	//Build helper variables
	int type;
	ll a;
	ll b;
	ll cur;
	vector<ll> res;

	//Main loop
	//Read a query, disect which type it is
	//and then perform the according action
	REP(i,0,q){
		//Read in query
		cin >> type;
		cin >> a;
		cin >> b;
		//If update query
		if(type==1){
			cur = n+a-1;
			seg[cur] = b;
			cur /= 2;
			while(cur >= 1){
				seg[cur] = min(seg[2*cur], seg[2 * cur + 1]);
				cur /= 2;
			}
		}
		//If min query
		else if(type==2){
			a += n-1;
			b += n-1;
			cur = 10000000001;
			while(a <= b){
				if(a%2 == 1){
					cur = min(cur, seg[a++]);
				}
				if(b%2 == 0){
					cur = min(cur, seg[b--]);
				}
				a /= 2;
				b /= 2;
			}
			res.push_back(cur);
		}
	}

	//Write out
	for(auto v: res){
		cout << v << "\n";
	}	

	//Return
	return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED