[BOJ] 14438 : 수열과 쿼리 17

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int n, m, sqr, a[100001], bkt[100001];

void upd(int i, int v) {
	a[i] = v, bkt[i / sqr] = 1e9 + 1e8;
	int tmp = i / sqr;
	for (int j = tmp * sqr; j < (tmp + 1) * sqr; j++) bkt[tmp] = min(bkt[tmp], a[j]);
}

int qry(int i, int j) {
	int ret = 1e9 + 1e8;
	while (i % sqr && i <= j) ret = min(ret, a[i++]);
	while ((j + 1) % sqr && i <= j) ret = min(ret, a[j--]);
	while (i <= j) ret = min(ret, bkt[i / sqr]), i += sqr;
	return ret;
}

int main() {
	scanf("%d", &n);
	sqr = sqrt(n);
	for (int i = 0; i < n; i++) bkt[i] = 1e9 + 1e8;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		bkt[i / sqr] = min(bkt[i / sqr], a[i]);
	}
	scanf("%d", &m);
	while (m--) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) {
			upd(b - 1, c);
		}
		else {
			printf("%d\n", qry(b - 1, c - 1));
		}
	}
	return 0;
}