[9426] 중앙값 측정

https://www.acmicpc.net/problem/9426

예전엔 중앙값 관련 문제 풀때 PQ 2개를 두고 풀거나 (최대/최소 중앙값을 찾는경우)parametric search로 풀었던것 같은데 오랜만에 중앙값 문제를 봐서 그런지 전에 풀었던 풀이가 기억이 나지않아 좀 다른 방법으로 풀었다.

counting을 체크하는 리프노드가 65536개 짜리인 indexed tree를 구성하고, 최초 k개의 입력된 숫자를 indexed tree에 update한 뒤 중앙값인(k+1)/2번째 숫자가 어디있는지를 indexed tree에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다.

마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식으로 N-K+1회 반복하면 답을 구할 수 있다.