Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

PKU 3784 - Running Median

問題 : Running Median

数が$N$ 個与えられる.
奇数個毎に, それまでの数の中央値を出力せよ.

テストケース数$T \leqq 1000$
$N \leqq 9999$
$N$ は奇数


解答 :
数を加算するセグメント木(BIT でも良い) があれば, それをなぞるように降りていけば良い.
計算量は$O(TN\log N)$ となる.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int segt[32768];

void update(int k)
{
	k += 16383;
	
	segt[k]++;
	while (k){
		k = (k - 1) / 2;
		segt[k] = segt[k * 2 + 1] + segt[k * 2 + 2];
	}
}

int traverse(int x, int c = 0, int k = 0, int l = 0, int r = 16384)
{
	if (r - l == 1) return (l);
	if (c + segt[k * 2 + 1] < x) return (traverse(x, c + segt[k * 2 + 1], k * 2 + 2, l + r >> 1, r));
	return (traverse(x, c, k * 2 + 1, l, l + r >> 1));
}

int main()
{
	int T;
	int N, M;
	int A[9999];
	
	scanf("%d", &T);
	
	while (T--){
		scanf("%d %d", &N, &M);
		vector<int> v(M);
		for (int i = 0; i < M; i++){
			scanf("%d", A + i);
			v[i] = A[i];
		}
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		
		memset(segt, 0, sizeof(segt));
		
		printf("%d %d\n", N, (M + 1) / 2);
		for (int i = 0; i < M; i++){
			update(lower_bound(v.begin(), v.end(), A[i]) - v.begin());
			if (i % 2 == 0){
				printf("%d%c", v[traverse(i / 2 + 1)], " \n"[(i / 2 + 1) % 10 == 0 || i == M - 1]);
			}
		}
	}
}