动态中位数（对顶堆）

题意：动态求当前序列中的中位数
思路：为了动态维护中位数，我们可以建立两个二叉堆：一个小跟堆、一个大根堆。在依次读入这个整数序列的过程中，设当前序列长度为M，我们始终保持：
1.序列中从小到大排名为1-M/2的整数储存在大根堆中
2.序列中从小到大排名为M/2-M的整数储存在小根堆中。
任何时候，如果某一个堆中元素个数过多，打破了这个性质，就取出该堆的堆顶插入到另一个堆。这样一来，序列的中位数就是小根堆的堆顶了。

每次新读入一个数值X后，若X比中位数小，则插入大根堆，否则插入小根堆，在插入后检查并维护上述性质即可。
这就是“对顶堆”算法

#pragma GCC optimize(3,"Ofast","inline")  	//G++
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fcout cout<<setprecision(4)<<fixed
using namespace std;
typedef long long ll;
//======================================
namespace FastIO{
char print_f[105];void read() {}void print() {putchar('\n');}
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth){x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)){if (ch == '-')f *= -1;ch = getchar();}while (isdigit(ch)){x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}
template <typename T, typename... T2>
inline void print(T x, T2... oth){ll p3=-1;if(x<0) putchar('-'),x=-x;do{print_f[++p3] = x%10 + 48;}while(x/=10);while(p3>=0) putchar(print_f[p3--]);putchar(' ');print(oth...);}} // namespace FastIO
using FastIO::print;
using FastIO::read;
//======================================
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn = 5e5+5;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    clock_t c1 = clock();
#endif
//**************************************
    int T;
    read(T);
    while(T--){
        int num,n;
        read(num,n);
        print(num,(n+1)/2);
        priority_queue<int>q1; //大根堆 存前1-n/2个数
        priority_queue<int,vector<int>,greater<int>>q2; //大根堆 存前n/2+1-n个数
        for(int i=1,x;i<=n;i++){
            read(x);
            if(q2.empty()||x>=q2.top()) q2.push(x);
            else q1.push(x);
            if(q1.size()>i/2) q2.push(q1.top()),q1.pop();
            if(q2.size()>(i+1)/2) q1.push(q2.top()),q2.pop();
            if(i&1){
                cout<<q2.top();
                putchar((i+1)/2%10==0?'\n':' ');
            }
        }
        if((n+1)/2%10)
            cout<<"\n";
    }
//**************************************
    
#ifndef ONLINE_JUDGE
    cerr << "Time:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}
 */