[2357] 최솟값과 최댓값

2023. 2. 15. 17:59

2357번: 최솟값과 최댓값

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

www.acmicpc.net

세그먼트 트리 문제다.

각 노드에 (Int, Int) 자료형을 통해 최솟값과 최댓값을 담는 세그먼트 트리를 생성하여, 각 구간별 최솟값과 최댓값이 담기는 세그먼트 트리를 생성하여 조건에 맞게 출력하면 된다.

[1,2,3,4,5] 배열을 기준으로 만든 세그먼트 트리다. 리프노드에는 동일한 값을 넣었다.

트리를 읽어야 할 때는 구간에 해당하는 노드를 탐색, 각각의 최댓값과 최솟값을 비교하여 반환하면 된다.

해당 그림은 1 ~ 4번 인덱스 구간의 최솟값, 최댓값을 읽어올 때 참고하게 될 노드다.

범위 밖의 노드라면 입력 범위의 최댓값과 최솟값을 바꾸어 출력하게 하였다. ((1,000,000,000, 1) 리턴)

Hyun's_Devlog