[백준 2357] 최솟값과 최댓값 (C++)

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

문제

---

 

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 

입력

---

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

 

출력

---

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

 

문제 풀이

---

세그먼트 트리 문제.

합을 구하는 세그먼트 트리 대신 최솟값과 최댓값을 구하는 세그먼트 트리를 만들어주면 된다.

초기화는 리프 노드라면 노드 번호에 해당하는 배열의 값 그 자체를, 아니라면 두 자식의 합 대신 두 자식 중 큰 값/작은 값을 세그먼트 트리에 저장한다.

a~b 사이의 가장 큰 값/ 가장 작은 값을 구할 때에는 범위에 해당한다면 세그먼트 트리의 값 자체를, 아니라면 두 자식 중 큰 값/작은 값을 반환해주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int* arr;
int* maxSegTree;
int* minSegTree;

int initMin(int start, int end, int nodeNum)
{
	if (start == end)
	{
		return minSegTree[nodeNum] = arr[start];
	}
	else
	{
		int mid = (start + end) / 2;
		return minSegTree[nodeNum] = min(initMin(start, mid, nodeNum * 2), initMin(mid + 1, end, nodeNum * 2 + 1));
	}
}

int initMax(int start, int end, int nodeNum)
{
	if (start == end)
	{
		return maxSegTree[nodeNum] = arr[start];
	}
	else
	{
		int mid = (start + end) / 2;
		return maxSegTree[nodeNum] = max(initMax(start, mid, nodeNum * 2), initMax(mid + 1, end, nodeNum*2 + 1));
	}
}

int getMin(int left, int right, int start, int end, int nodeNum)
{
	if (left > end || right < start)
	{
		return 1000000000;
	}
	else if (left <= start && end <= right)
	{
		return minSegTree[nodeNum];
	}
	else
	{
		int mid = (start + end) / 2;
		return min(getMin(left, right, start, mid, nodeNum * 2), getMin(left, right, mid + 1, end, nodeNum * 2 + 1));
	}
}

int getMax(int left, int right, int start, int end, int nodeNum)
{
	if (left > end || right < start)
	{
		return 0;
	}
	else if (left <= start && end <=right)
	{
		return maxSegTree[nodeNum];
	}
	else
	{
		int mid = (start + end) / 2;
		return max(getMax(left, right, start, mid, nodeNum * 2), getMax(left, right, mid + 1, end, nodeNum * 2+1));
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int a, b;
	cin >> N >> M;
	arr = new int[N];
	maxSegTree = new int[4 * N];
	minSegTree = new int[4 * N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	initMin(0, N - 1, 1);
	initMax(0, N - 1, 1);
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		cout << getMin(a-1, b-1, 0, N-1, 1) << " " << getMax(a - 1, b - 1, 0, N - 1, 1) << "\n";
	}
	return 0;
}