백준 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이하의 값을 갖는다.

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

구간별 최소 및 최대를 구하는 세그먼트 트리 문제이다. 여기서 최소를 담당하는 세그먼트 트리와 최대를 담당하는 세그먼트 트리, 총 두 개의 트리를 만들어서 사용하면 된다.

seg1[]이 최소, seg2[]가 최대이다. 따라서 세그먼트 트리에 관련한 함수도 2개씩 만들어주었다. 크게 어려운 것은 없다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int n, a[100000], seg1[400000], seg2[400000];

int construct1(int start, int end, int idx)
{
	if (start == end) {
		seg1[idx] = a[start];
		return seg1[idx];
	}
	int mid = (start + end) / 2;
	seg1[idx] = min(construct1(start, mid, idx * 2 + 1), construct1(mid + 1, end, idx * 2 + 2));

	return seg1[idx];
}

int construct2(int start, int end, int idx)
{
	if (start == end) {
		seg2[idx] = a[start];
		return seg2[idx];
	}
	int mid = (start + end) / 2;
	seg2[idx] = max(construct2(start, mid, idx * 2 + 1), construct2(mid + 1, end, idx * 2 + 2));

	return seg2[idx];
}

int Min(int l, int r, int il, int ir, int idx)
{
	if (l > ir || r < il) return 10000000000;
	if (il <= l && ir >= r) return seg1[idx];
	int mid = (l + r) / 2;
	return min(Min(l, mid, il, ir, idx * 2 + 1), Min(mid + 1, r, il, ir, idx * 2 + 2));
}

int Max(int l, int r, int il, int ir, int idx)
{
	if (l > ir || r < il) return 1;
	if (il <= l && ir >= r) return seg2[idx];
	int mid = (l + r) / 2;
	return max(Max(l, mid, il, ir, idx * 2 + 1), Max(mid + 1, r, il, ir, idx * 2 + 2));
}

int main()
{
	int m, in1, in2;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	construct1(0, n - 1, 0);
	construct2(0, n - 1, 0);

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &in1, &in2);
		printf("%d %d\n", Min(0, n - 1, in1 - 1, in2 - 1, 0), Max(0, n - 1, in1 - 1, in2 - 1, 0));
	}

	return 0;
}