Running Median

思路：

用两个优先队列，一个维护大的一半，一个维护小的一半，小的一半放在根结点最大的优先队列q1里，大的一半放在根结点最小的优先队列q2里，如果q1中的数比q2多1个以上，就把q1的顶点移到q2中去；如果q2中的数比q1多1个以上，就把q2的顶点移到q1中去。
如果q1.size()比q2.size()多一个，中位数就是q1的根，因为q1下面的数都比它小，q2里的数都比它大，而且q1的子树中结点的数量和q2中结点的数量一样多，那么q1的根结点不就是中位数了吗；反之也是一样。

以为这样就能ac了吗？

没错，是可以ac了，如果是我这样的菜鸡就选c++14的编译环境提交，如果选了c++11用我的代码提交，稳稳的内存超限。

#include <bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int t,m,n,x;
int main() {
    js;
    cin>>t;
    while(t--) {
        priority_queue<int> q1;
        priority_queue<int, vector<int>, greater<int> > q2;
        cin>>m>>n>>x;
        q1.push(x);
        cout<<m<<" "<<(n>>1)+1<<endl;
        cout<<x<<" ";
        for(int i=2;i<=n;++i) {
            cin>>x;
            if(x<q1.top())    q1.push(x);
            else q2.push(x);
            if(q2.size()>q1.size()+1) {
                q1.push(q2.top());
                q2.pop();
            }
            if(q1.size()>q2.size()+1) {
                q2.push(q1.top());
                q1.pop();
            }
            if(i&1) {
                if(q1.size()>q2.size())    cout<<q1.top()<<" ";
                else cout<<q2.top()<<" ";
            }
            if(i%20==0)    cout<<endl;
        }
        if(n%20)    cout<<endl;
    }
    return 0;
}