BOJ 9345(디지털 비디오 디스크(DVDs)) 풀이

세그먼트 트리 min,max를 이용한 풀이입니다

 

solved.ac 티어 : 플래티넘 3

www.acmicpc.net/problem/9345

9345번: 디지털 비디오 디스크(DVDs)

 

이 문제를 풀려면 구간의 최솟값과 최댓값을 구해야합니다 그 이유는 만약 A가 1부터 4까지의 구간의 책을 가지고 왔습니다.

 

이때 1부터 4까지의 책들이 순서는 상관없이 모두 있어야합니다. 만약 1부터 4까지의 최솟값이 1이 아니라면 1보다 작은 값이 들어있거나 1은 들어있지 않게 되는거고 최댓값이 4가 아니라면 4보다 큰값이 들어있거나 4가 들어있지 않게 됩니다.

 

그렇기 때문에 min,max로 구간의 시작과 끝이랑 비교를 했을때 시작 위치 = min 그리고 끝위치 = max일경우 yes를 출력하고 나머지는 no를 출력하면 되고 변경은 일반 세그먼트 트리 변경처럼 두 위치를 바꿔서 변경해주시면 됩니다.