题解 | #Running Median#

考虑到在单调序列下中位数左边都是大于（小于）中位数的数，右边都是小于（大于）中位数的数，因此可构建两个堆来维护中位数的左右序列，同时维护两个堆的长度差的绝对值不大于1即可

#include <bits/stdc++.h>
using namespace std;
int p,m,tmp,num;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int ct;
    cin>>p;
    while(p--){
        cin>>tmp>>m;
        cout<<tmp<<' '<<(m+1)/2<<'\n';
        priority_queue<int,vector<int>,less<int>> heap_max;
        priority_queue<int,vector<int>,greater<int>> heap_min; 
        ct = 0;
        for(int i = 1;i <= m;i++){
            cin>>num;
            //先考虑把元素压入堆中
            if(i == 1) heap_max.push(num);    //第一个元素默认压入左堆
            else if(i == 2){
                if(num >= heap_max.top()) heap_min.push(num);
                else{
                    heap_min.push(heap_max.top());
                    heap_max.pop();
                    heap_max.push(num);
                }
            }
            else{
                if(num >= heap_min.top()) heap_min.push(num);
                else heap_max.push(num);
            }
            
            //再考虑维护堆的长度
            if(heap_max.size() > heap_min.size()+1){
                heap_min.push(heap_max.top());
                heap_max.pop();
            }
            else if(heap_min.size() > heap_max.size()+1){
                heap_max.push(heap_min.top());
                heap_min.pop();
            }
            
            //最后输出中位数，即较长堆的堆顶元素
            if(i%2){
                ct++;
                if(heap_max.size() > heap_min.size()) cout<<heap_max.top()<<' ';
                else cout<<heap_min.top()<<' ';
                if(ct%10 == 0) cout<<'\n';
            }
        }
        if(ct%10 != 0) cout<<'\n';
    }
    return 0;
}