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]); } } } }