문제

출처 : https://www.algospot.com/judge/problem/read/RUNNINGMEDIAN

한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때는 가운데 있는 두 값 중 보다 작은 것을 수열의 중간값이라고 정의하도록 합시다.

한 수열의 중간값은 수열에 새로운 수가 추가될 때마다 바뀔 수 있습니다. 텅 빈 수열에서 시작해서 각 수가 추가될 때마다 중간값을 계산하는 프로그램을 작성하세요. 예를 들어 3, 1, 5, 4, 2 순서대로 숫자가 추가될 경우 수열의 중간값은 3, 1, 3, 3, 3 순서로 변화합니다.

입력 생성

입력의 크기가 큰 관계로, 이 문제에서는 수열을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.

• A[0] = 1983
• A[i] = (A[i-1] * a + b) % 20090711

a와 b는 입력에 주어지는 상수입니다. 이 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다.

입력

입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C줄에 각 3개의 정수로 수열의 길이 N (1 <= N <= 200,000), 그리고 수열을 생성하는 데 필요한 두 정수 a , b (0 <= a,b <= 10000) 가 주어집니다.

출력

각 테스트 케이스마다 한 줄에 N개의 중간값의 합을 20090711로 나눈 나머지를 출력합니다.

풀이

우선순위 큐를 활용하여 중간값을 추출할 수 있는데, 수열 중 중간값 mid를 기준으로 작은 왼쪽 부분수열에 대한 우선순위큐와, 큰 오른쪽 부분수열에 대한 우선순위큐를 구현한다. 이 때, 왼쪽 부분수열은 가장 큰 값을 추출하기 위해 크기가 큰 값 순으로 저장되는 우선순위큐를, 오른쪽 부분수열은 가장 작은 값을 추출하기 위해 크기가 작은 값으로 저장되는 우선순위큐를 사용한다.

int mid = 0;
double num = 0;
int sum = 0;
for (int j = 0; j < n; j++) {
	if (j == 0) {
		mid = 1983;
		num = 1983;
	}
	else {
		num = ((num * a) + b) % MOD;
		if (j % 2 == 1) {
			if (mid > num) {
				pq_left.add((int)num);
				pq_right.add(mid);
				mid = pq_left.poll();
			} else
				pq_right.add((int)num);
		} else {
			if (mid < num) {
				pq_right.add((int)num);
				pq_left.add(mid);
				mid = pq_right.poll();
			} else
				pq_left.add((int)num);
		}
	}
sum += mid;
sum %= MOD;

수열에 새로운 수가 들어올 때 mid값이 변화하는 경우는 홀/짝의 경우와 mid값의 대소에 따라 결정된다.

수열의 개수를 기준으로 값이 추가되었을 때, 짝수의 경우는 중간값보다 작은 값이 들어온 경우 해당 값을 왼쪽 큐에 추가하고 기존 mid값을 오른쪽 큐에 추가 한 다음, 왼쪽 큐 중 가장 큰 값을 꺼내 mid값으로 설정하여 mid값이 오른쪽으로 밀리는 것을 구현한다. 홀수의 경우는 중간값보다 큰 값이 들어온 경우 오른쪽 큐에 추가하고 기존 mid값을 왼쪽 큐에 추가한 다음, 오른쪽 큐 중 가장 작은 값ㅇ르 꺼내 mid값으로 설정하여 mid값이 왼쪽으로 밀리는 것을 구현한다.