大家好，这里是可爱的 Sora 酱~ 是一枚热爱算法的女孩子！

题目要求支持动态插入和查询中位数。我们可以转换成动态插入和知 rank 查数。

所以考虑使用平衡树，但是平衡树很不好写，所以我们用动态数组代替。

C++ 代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
    int num, n;
    vector<int> a;
    vector<int>::iterator vit;
    cin >> num;
    cin >> n;
    cout << num << ' ' << (n + 1) / 2 << endl;
    int ed = 0;
    for(int i = 1, x; i <= n; i ++) {
        cin >> x;
        vit = lower_bound(a.begin(), a.end(), x);
        a.insert(vit, x);
        if(i % 2) { cout << a[(i + 1) / 2 - 1] << ' '; ed ++; }
        if(ed == 10 && i < n) {cout << endl; ed = 0;}
    } cout << endl;
}
int main() {
    int p;
    cin >> p;
    while(p --) solve();
}