https://www.acmicpc.net/problem/5817
접근법
- 구간트리
- 난쟁이키 = 난쟁이 인덱스로 봐도 무방함
- [난쟁이 인덱스] = 위치
- 구간트리(난쟁이 인덱스, 난쟁이 인덱스) = (최소값, 최대값)
- 난쟁이 위치들의 최소값 ~ 최대값 사이에 난쟁이들이 딱 맞게 들어갈 수 있으면 서로 이웃 한 것임 : 빈공간이 없다는 뜻
- 위치를 서로 바꾸는 경우도 있으므로 [위치] = 난쟁이 인덱스 배열도 유지 필요
주의점
- 구간트리를 사용하지 않고 가장 작은 난쟁이 ~ 가장 큰 난쟁이 위치만으로는 판단 할 수 없음 예를 들어
- 2 100 102 103 6 와 같은 경우 2 와 6 사이에 위치만으로 보면 3개의 난쟁이가 존재한다고 판단할 수 있으나,
- 3, 4, 5 의 난쟁이가 있다고는 볼 수 없기 때무임
newbieski