【每日一题】Running Median

对顶堆，开两个堆，一个是大根堆，一个是小根堆，然后小于中位数的都放在大根堆，大于中位数的都放在小根堆，维护两个堆的size相等或差为1即可，这样多出来的数即为中位数。

#include <bits/stdc++.h>
using namespace std;
int t,n,num;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int>>q2;
vector<int>v;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>num>>n;
        v.clear();
        while(!q1.empty())
        q1.pop();
        while(!q2.empty())
        q2.pop();
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(i&1)
            {
                q2.push(x);
                q1.push(q2.top());
                q2.pop();
            }
            else
            {
                q1.push(x);
                q2.push(q1.top());
                q1.pop();
            }
            if(i&1)
                v.push_back(q1.top());
        }
        cout<<num<<' '<<v.size()<<'\n';
        for(int i=0;i<v.size();i++)
        {
            cout<<v[i]<<' ';
            if(i%10==9)
                cout<<'\n';
        }
        if((v.size()-1)%10!=9)
        cout<<'\n';
    }
    return 0;
}