Running Median
维护中位数
构建两个堆，一个大根堆，一个小根堆
为了确保某一对顶是中位数（实操时选择小根堆）要维护下列性质（当前扫到第 \(m\) 个元素）：
- 大根堆的大小是 \(\left\lfloor\dfrac{m}{2}\right\rfloor\)
- 小根堆的大小是 \(\left\lceil\dfrac{m}{2}\right\rceil\)
小根堆维护技巧：存 \(-x\) 这样绝对值大的就在前面了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std ;
const int N = 1000010 ;
priority_queue <int> hpx, hpn ; // max heap & min heap
vector <int> ans ;
int rnd, rid, n, xnum, nnum ;
int a[N] ;
int main() {
scanf("%d", &rnd) ;
while (rnd--) {
scanf("%d%d", &rid, &n) ;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]) ;
ans.clear() ; ans.push_back(a[1]) ;
while (!hpx.empty()) hpx.pop() ;
while (!hpn.empty()) hpn.pop() ;
hpn.push(-a[1]) ; nnum = 1 ; xnum = 0 ;
for (int i = 2; i <= n; i++) {
if (a[i] < -hpn.top()) {
hpx.push(a[i]) ;
xnum++ ;
} else {
hpn.push(-a[i]) ;
nnum++ ;
}
while (nnum > i - i / 2) {
hpx.push(-hpn.top()) ; hpn.pop() ;
nnum-- ; xnum++ ;
}
while (xnum > i / 2) {
hpn.push(-hpx.top()) ; hpx.pop() ;
xnum-- ; nnum++ ;
}
if (i % 2 == 1) ans.push_back(-hpn.top()) ;
}
printf("%d %d\n", rid, n / 2 + 1) ;
for (int i = 0; i < ans.size(); i++) {
printf("%d", ans[i]) ;
if (i == ans.size() - 1) puts("") ;
else if (i % 10 == 9) puts("") ;
else printf(" ") ;
}
}
}