[알고리즘] 최솟값과 최댓값

구현 방식

• 세그먼트 트리 방식으로 최대값, 최소값을 구한다.
• 출력이 많이 나올 수 있으므로 (최대 10000번) 아래 입출력 동기화 부분을 작성한다.

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

void solution(int N, int M);
int InitMin(int start, int end, int node);
int InitMax(int start, int end, int node);
int GetMin(int start, int end, int node, int left, int right);
int GetMax(int start, int end, int node, int left, int right);


const int MAXSIZE = 100000;
long long tree_min[MAXSIZE * 4];
long long tree_max[MAXSIZE * 4];
int arr[MAXSIZE];



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	
	solution(N, M);
}

void solution(int N, int M)
{
	InitMin(0, N - 1, 1);
	InitMax(0, N - 1, 1);

	for (int i = 0; i < M; i++)
	{
		int left, right;
		cin >> left >> right;
		cout << GetMin(0, N-1, 1,left-1, right-1) << " " << GetMax(0, N-1, 1, left-1, right-1) << "\n";

	}
}

int InitMin(int start, int end, int node)
{
	if (start == end) return tree_min[node] = arr[start];
	int mid = (start + end) / 2;
	return tree_min[node] = min(InitMin(start, mid, node * 2), InitMin(mid + 1, end, node * 2 + 1));
}

int InitMax(int start, int end, int node)
{
	if (start == end) return tree_max[node] = arr[start];
	int mid = (start + end) / 2;
	return tree_max[node] = max(InitMax(start, mid, node * 2), InitMax(mid + 1, end, node * 2 + 1));
}

int GetMin(int start, int end, int node, int left, int right)
{
	if (right < start || end < left) return INT_MAX;
	if (left <= start && end <= right) return tree_min[node];
	int mid = (start + end) / 2;
	return min(GetMin(start, mid, node * 2, left, right), GetMin(mid + 1, end, node * 2 + 1, left, right));
}

int GetMax(int start, int end, int node, int left, int right)
{
	if (right < start || end < left) return INT_MIN;
	if (left <= start && end <= right) return tree_max[node];
	int mid = (start + end) / 2;
	return max(GetMax(start, mid, node * 2, left, right), GetMax(mid + 1, end, node * 2 + 1, left, right));
}