코드 복사/붙여넣기 하는 당신이 아름답습니다.

14438 : 수열과 쿼리 17

풀이

sqrt decomposition을 이용해서 풀었다.

물론 segment tree를 이용하면 훨씬 더 빠르다.

코드

#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;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-06-02 11:27

Read more posts by this author