rmq.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

class segtree {
		vector<int> data;
		int n = 1;
		int query(int a, int b, int k, int l, int r) {
			if (b <= l || r <= a) return INF;
			if (a <= l && r <= b) return data[k];
			int left = query(a, b, k*2+1, l, (l+r)/2),
			    right = query(a, b, k*2+2, (l+r)/2, r);
			return min(left, right);
		}
	public:
		int const INF = numeric_limits<int>::max();
		segtree(int n_) {
			while (n_ > n) n *= 2;
			data.resize(2*n-1, INF);
		}
		void update(int k, int a) {
			k += n-2;
			data[k] = a;
			while (k > 0) {
				k = (k-1)/2;
				data[k] = min(data[k*2+1], data[k*2+2]);
			}
		}
		inline int query(int a, int b) { return query(a-1, b, 0, 0, n); }
};

int main() {
	int N, Q;
	cin >> N >> Q;
	segtree rmq(N);
	for (int i = 1; i <= N; i++) {
		int a;
		cin >> a;
		rmq.update(i, a);
	}
	for (int i = 0; i < Q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		if (type == 1) cout << rmq.query(a, b) << endl;
		else rmq.update(a, b);
	}
	return 0;
}