[C++] 10868: 최소값

골드1이던가 아니던가

 

#include <iostream>
#include <algorithm>
#define INF 1000000001
using namespace std;
int N, M;

int baseNum = 1;
int IDT[300000];

void treeUpdate(int i, int newNum) {
	int idx = i - 1 + baseNum;
	IDT[idx] = newNum;

	while (idx /= 2) {
		int lci = idx * 2;
		int rci = lci + 1;
		IDT[idx] = min(IDT[lci], IDT[rci]);
	}
}

int treeMin(int i, int j) {
	int li = i - 1 + baseNum;
	int ri = j - 1 + baseNum;

	int m = 1000000001;
	while (li <= ri) {
		if (li % 2 == 1) m = min(m, IDT[li]);
		if (ri % 2 == 0) m = min(m, IDT[ri]);
		li = (li + 1) / 2;
		ri = (ri - 1) / 2;
	}
	return m;
}


int main() {
	scanf("%d%d", &N, &M);
	while (baseNum < N) {
		baseNum <<= 1;
	}
	for (int i = 0; i < 2 * baseNum; i++) {
		IDT[i] = INF;
	}
	int num;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &num);
		treeUpdate(i, num);
	}
	int a, b;
	while (M--) {
		scanf("%d%d", &a, &b);
		printf("%d\n", treeMin(a, b));
	}
}