이동식 저장소

1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 길이 $N$인 수열에 대해 중앙값 내지는 중간값을 연속적으로 구하는 문제이다. 잘 알려진 대로(하지만 모르면 모르는) 세그먼트 트리를 응용하여 풀 수 있다. 값의 범위가 $[0,~65536]$으로 꽤 작아서, 각 값이 등장한 횟수를 저장해 놓은 뒤 합이 mid가 되는 최소의 인덱스를 찾으면 된다. 나는 ``std::multiset`` 두 개를 사용하여 풀었다. 길이 $K$인 구간을 ``left``와 ``right..