[ 백준 2357 ] 최솟값과 최댓값 (C++, 세그먼트 트리)

[문제보기]

 

[해결과정]

 - 세그먼트 트리 활용

 

1. minTree, maxTree 구별

2. 각각 init함수와 query함수 작성

 

[소스코드]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;

typedef long long ll;
#define MAX 400005

int n, m, a, b;
ll minTree[MAX*10];
ll maxTree[MAX*10];
ll node[MAX];

// init(배열, 위치, 시작점, 끝점)
// init_최소 트리
ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (dataIdxL == dataIdxR) return minTree[treeIdx] = arr[dataIdxL - 1];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return minTree[treeIdx] = min(minInit(arr, 2 * treeIdx, dataIdxL, mid), minInit(arr, 2 * treeIdx + 1, mid + 1, dataIdxR));
}
// init_최대 트리
ll maxInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (dataIdxL == dataIdxR) return maxTree[treeIdx] = arr[dataIdxL - 1];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return maxTree[treeIdx] = max(maxInit(arr, 2*treeIdx, dataIdxL, mid), maxInit(arr, 2*treeIdx+1, mid+1, dataIdxR));
}

// query(시작위치, 끝위치, 위치, 시작점, 끝점)
// 최소 트리
ll minQuery(ll queryL, ll queryR, ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (queryL > dataIdxR || dataIdxL > queryR) return 1000000001;
	if (dataIdxL >= queryL && queryR >= dataIdxR) return minTree[treeIdx];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return min(minQuery(queryL, queryR, 2 * treeIdx, dataIdxL, mid), minQuery(queryL, queryR, 2 * treeIdx + 1, mid + 1, dataIdxR));
}
// 최대트리
ll maxQuery(ll queryL, ll queryR, ll treeIdx, ll dataIdxL, ll dataIdxR) {
	if (queryL > dataIdxR || dataIdxL > queryR) return -1000000001;
	if (dataIdxL >= queryL && queryR >= dataIdxR) return maxTree[treeIdx];
	ll mid = (dataIdxL + dataIdxR) / 2;
	return max(maxQuery(queryL, queryR, 2 * treeIdx, dataIdxL, mid), maxQuery(queryL, queryR, 2 * treeIdx + 1, mid + 1, dataIdxR));
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// input
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> node[i];

	// init
	minInit(node, 1, 1, n);
	maxInit(node, 1, 1, n);

	// query
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << minQuery(a, b, 1, 1, n) << " " << maxQuery(a, b, 1, 1, n) << "\n";
	}
	

	// debug
	/*
	for (int i = 0; i < n * 6; i++) cout << minTree[i] << " ";
	cout << endl;
	for (int i = 0; i < n * 6; i++) cout << maxTree[i] << " ";
	*/

	return 0;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 - 실수한 부분

  1. query 내부에서 배열에 해당되지 않는 부분을 각각 가능한 최대(혹은 최소)의 수(1000000001, -1000000001)를 리턴 하지 않았던 점.

  2. 1에서 최대의 수를 문제에서 지정한 범위까지 지정하지 않았던 점.

 

[관련 문제 혹은 비슷한 문제]

 세그먼트 트리