Byeo

boj 9345 목차 개요 설명 코드 개요 boj 9345 - 디지털 비디오 디스크(DVDs) 문제도 segment tree를 응용한 문제입니다. Query 0 이 들어왔을 때는 DVD 배열에서 a번째와 b번째의 값을 바꿔주면 되고, Query 1이 들어왔을 때는 a ~ b 의 구간을 검색하면 됩니다. 얼핏 보기에는 segment tree를 어떻게 응용해야 하는 지에 대해 의문이 들 수 있습니다. 하지만 잘 살펴보면, Query 1이 들어왔을 때는 "a ~ b 의 구간에서 DVD가 a번부터 b번까지 모두 존재하는가" 를 살펴 보면 됩니다. 문제를 바꾸면, a ~ b 구간에서 중간 DVD를 살펴 볼 필요 없이 최솟값과 최댓값을 살펴보면 됩니다. 즉, a ~ b 구간의 최솟값이 a이면서, 최댓값이 b라면 조..