devbelly

문제 https://www.acmicpc.net/problem/9426 알고리즘 세그먼트 트리 풀이 $N$초동안 온도를 기록하는데 최근 $K$초의 중앙값들을 모두 더하는 것을 요구하는 문제입니다. 이 문제의 경우는 이전의 값을 삭제하는 연산 없이 계속 추가한 후 중앙값만 처리하면 되므로 최대 힙, 최소 힙 두 개로 $O(NlogN)$에 해결 가능했으나, 가장 최근$K$초의 중앙값만을 계속 구해야 하므로 최근 K초를 제외한 온도를 삭제할 수 있는 자료구조인 세그먼트 트리를 활용하겠습니다. 문제에서 요구하는 핵심쿼리는 중앙값 처리입니다. 트리에서의 인덱스는 온도를 의미합니다. 온도의 개수를 누적시킨다면, 인덱스에 따라 값들이 오름차순으로 정렬되어 있으므로, 이분 탐색을 통해 중앙값을 빠르게 처리할 수 있습니..