[BOJ] 백준 2357번: 최솟값과 최댓값

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

https://belepi.tistory.com/8 에서 다룬 백준 10868번: 최솟값을 풀어봤을 경우 쉽게 접근할 수 있는 문제입니다.

모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다.

 

#include <bits/stdc++.h>
#define SIZETR (262144) // 2^18
using namespace std;

const int INF = 0x7fffffff;
int N, M, a[100001], l, r;
int minTree[SIZETR], maxTree[SIZETR];
int OFFSET = 1;

void init(){
	while(OFFSET < N) OFFSET <<= 1;
	for(int i = 0; i < N; ++i){
		minTree[OFFSET + i] = a[i];
		maxTree[OFFSET + i] = a[i];
	}
	for(int i = N; i < OFFSET; ++i){
		minTree[OFFSET + i] = INF;
		maxTree[OFFSET + i] = 0;
	}
	for(int i = OFFSET-1; i > 0; --i){
		minTree[i] = min(minTree[i<<1], minTree[(i<<1) + 1]);
		maxTree[i] = max(maxTree[i<<1], maxTree[(i<<1) + 1]);
	}
}

int minQuery(int left, int right){
	left += (OFFSET - 1);
	right += (OFFSET - 1);
	int res = INF;
	while(left <= right){
		if(left % 2 == 1) res = min(res, minTree[left++]);
		if(right % 2 == 0) res = min(res, minTree[right--]);
		left >>= 1;
		right >>= 1;
	}
	return res;
}

int maxQuery(int left, int right){
	left += (OFFSET - 1);
	right += (OFFSET - 1);
	int res = 0;
	while(left <= right){
		if(left % 2 == 1) res = max(res, maxTree[left++]);
		if(right % 2 == 0) res = max(res, maxTree[right--]);
		left >>= 1;
		right >>= 1;
	}
	return res;
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	
	for(int i = 0; i < N; ++i){
		cin >> a[i];
	}
	
	init();
	
	while(M--){
		cin >> l >> r;
		cout << minQuery(l,r) << ' ';
		cout << maxQuery(l,r) << '\n';
	}
}

 

이전 문제와 달리 최솟값뿐만 아니라 최댓값도 출력해야 하기 때문에 구간의 대푯값으로 최솟값을 저장하는 minTree와 최댓값을 저장하는 maxTree를 init() 함수에서 구현하였고 각 tree를 이용해 query를 처리하는 minQuery 함수와 maxQuery 함수를 구현하였습니다.

 

init() 함수에서 leaf node의 빈 구간에 저장하는 값에 유의해주세요. minTree는 INF, maxTree는 0을 저장하였습니다. 문제에서 입력으로 1 이상 10억 이하의 정수가 주어지므로 minTree의 INF 값으로는 (10억 + 1) 이상의 값이면 상관없으며 maxTree는 0 이하의 값이면 상관없습니다. 저는 INF에는 충분히 큰 값으로 0x7fffffff를 사용했습니다.