1 2 3 4 5 6 7 8 9
1 2 3 4 5
只需要知道中间数
不需要知道小的那一堆和大的那一堆进行排序

小根堆up  __ 
          \/
大根堆down .
          / \
          ---

只需维护
1
当输入是偶数时 上面下面一样多
当输入是奇数时 下面比上面多一个

即下面个数最多比上面多1
2
小根堆的最小值比大根堆的最大值要大

即上面所有元素≥下面所有元素

假设已经维护好这样一个结构
进来一个x

先维护条件2
分情况
1 x≤大根堆堆顶 把x插入大根堆(下)
2 x>大根堆堆顶 把x插入小根堆(上)

插入完x 再维护条件1
分情况
1 如果下面太多(cnt[下]-cnt[上]>=2) 就把大根堆堆顶插入上面
2 如果上面太多(cnt[上]-cnt[下]>0) 就把小根堆堆底插入下面

则中位数即为下面大根堆的堆顶

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n, m;
        scanf("%d%d", &m, &n);
        printf("%d %d\n", m, (n + 1) / 2);//数据集编号 动态中位数个数
        //用优先队列实现堆
        priority_queue<int> down;//大根堆 /\

        priority_queue<int, vector<int>, greater<int>> up;//小根堆\/

        int cnt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int x;
            scanf("%d", &x);
            //如果下面为空 或者x比下面堆顶小 插入下面
            if (down.empty() || x <= down.top()) down.push(x);
            //否则 插入上面
            else up.push(x);
            //如果下面太多 cnt[下]-cnt[上]>=2 把下面堆顶挪上去
            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();
            //如果上面太多 cnt[上]-cnt[下]>0  把上面堆底挪下来
            if (up.size() > down.size()) down.push(up.top()), up.pop();
            //始终维护cnt[下]-cnt[上]=1 || 0
            if (i % 2)//第奇数个
            {
                printf("%d ", down.top());//打印下面堆顶
                if ( ++ cnt % 10 == 0) puts("");//每10个换行
            }
        }
        if(cnt % 10) puts("");
    }
    return 0;
}