[백준 / BOJ] 10868 최솟값

문제

10868번: 최솟값

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

www.acmicpc.net

N개의 숫자들을 입력받고 구간 (a,b)를 M번 입력받는다.

구간 a,b사이에서 가장 작은 값을 출력하는 문제다.

N과 M이 최대 10만이라 모든경우를 다 봐주면 1억번돌아서 시간초과가 나기때문에, 세그먼트 트리를 이용해서 각 구간을 빠르게 찾아줘야한다.

세그먼트 트리에 각 구간의 최솟값을 저장한다.

예제 1의 경우,

구간 1~10 에서의 최솟값은 5,

구간 1~5 : 30

구간 6~10 : 5

으로 저장해놓는다.

입력받을 받고 해당하는 구간내의 최솟값을 찾아 출력하면 끝

devxb/JJUNalgo

백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.

github.com