양방향 정렬 문제 해결: Chtholly Tree 활용
Chtholly Tree를 사용할 수 있는데 와선 세그먼트 트리를 쓰겠는가?
:::align{right}
——저우 슈겐
:::
평균 \(O((n + m) \log m)\) 시간 복잡도를 가지는 Chtholly Tree 기반 해결 방안을 제시합니다.
문제 개요
초기 수열 \([1 \dots n]\)이 주어지며, m번의 정렬 연산을 수행합니다:
\(p = 0\): 앞 \(q\)개를 내림차순 정렬
\(p = 1\): \(q\)부터 \(n\)까지를 오름 ...
8월 6일 17:10에 게시됨