solution

题目就是要求对于每奇数个数字，输出其中位数。

我们只要维护两个堆，第一个大根堆维护较小的数字，第二个小根堆维护较大的个数字。每当新加入一个数字的时候将其与大根堆的队首比较，并维护两个堆的大小。

要求的中位数就是大根堆里的最大值。

code

/*
* @Author: wxyww
* @Date: 2020-04-08 20:09:02
* @Last Modified time: 2020-04-08 20:20:57
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 10010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
priority_queue<ll>q1;
priority_queue<ll,vector<ll>,greater<ll> >q2;

int main() {
    // freopen("1.in","r",stdin);
    int T = read();
    while(T--) {
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        int num = read(),n = read();
        printf("%d %d\n",num,(n + 1) >> 1);
        q1.push(read());
        int now = 1;
        printf("%lld ",q1.top());
        for(int i = 2;i <= n;++i) {
            ll x = read();
            if(x > q1.top()) q2.push(x);
            else q1.push(x);
            if(i & 1) {
                while(q1.size() > q2.size()) {q2.push(q1.top());q1.pop();}
                while(q2.size() >= q1.size()) {q1.push(q2.top());q2.pop();}
                printf("%lld ",q1.top());
                ++now;
                if(now % 10 == 0) puts("");
            }
        }
        if(now % 10) puts("");
    }

    return 0;
}

/*
1
2 9 
9 8 7 6 5 4 3 2 1 
*/