依题意，求一个动态变化的长序列中位数，即快速动态求中位数

首先想到std::sort()，排序后输出序列中间位置的值即为中位数，显然对于n1长度的原始序列与n2长度的添加序列，有时间复杂度：

$O((n1+n2)log(n1+n2))O((n1+n2)log(n1+n2))$

当持续添加直到nx长度的序列，有总时间复杂度：

$O((n1+n2)log(n1+n2)+(n1+n2+n3)log(n1+n2+n3)+\mathrm{.}\mathrm{.}\mathrm{.}O((n1+n2)log(n1+n2)+(n1+n2+n3)log(n1+n2+n3)+...$ $\mathrm{.}\mathrm{.}\mathrm{.}+(n1+n2+\mathrm{.}\mathrm{.}\mathrm{.}+nx)log(n1+n2+\mathrm{.}\mathrm{.}\mathrm{.}+nx))...+(n1+n2+...+nx)log(n1+n2+...+nx))$

显然是没法过最后一个数据的(10200组)，当然你可以拿走前10/11的数据分

再想到中位数性质，不难发现，中位数mid需要维持它在长度为n的序列中(n为奇数)的顺序是[n/2]。进一步的，题目只需要找到中位数，不需要其余的序列保持有序或具有一定顺序，则序列lower[0...n/2-1]和upper[n/2+1...n-1]可以“无序”，但是要保证lower中所有数都小于mid，upper中所有数都大于mid

进一步的，堆这种数据结构刚好满足上述性质，并且堆的压入和弹出时间复杂度均为O(logN)

至此，以问题转化为：同时维护一个大根堆lower和小根堆upper，在加入新序列的数时，维护lower的根lower[0]比mid小（我们假设lower[0]是这个大根堆的根），upper的根upper[0]比mid大。同时我们不难发现一个性质：

① lower[1...n-1] <= lower[0] <= upper[0] <= upper[1...n-1]

显然，lower[0]或upper[0]甚至(lower[0] + upper[0]) / 2都可以作为中位数（当长度为偶数时取平均数），但必须满足lower序列的长度和upper序列的长度相差不超过1。根据题意，奇数长度一定存在中位数，此时中位数具有如下性质:

② mid = lower.size() > upper.size() ? lower[0] : upper[0]

综上所述，我们维护一个大根堆lower和小根堆upper，在加入新数val时，判断val <= upper[0]，为真则加入lower，反之则加入upper，这样即可维护性质①成立。最后我们检查lower和upper的长度相差是否超过1，若超过则较长的序列将根弹出，加入另一个序列，这样即可维护性质②成立。

分析时间复杂度

第一组加入序列：

$O(log(n1+1)+log(n1+2)+\mathrm{.}\mathrm{.}\mathrm{.}+log(n1+n2))=O(log(!(n1+n2))-(log1+log2+\mathrm{.}\mathrm{.}\mathrm{.}+logn1))=O((n1+n2)log(n1+n2)-n1logn1)O(log(n1+1)\; +\; log(n1+2)\; +\; ...\; +\; log(n1+n2))\; ~=\; O(log(!(n1+n2))\; -\; (log1\; +\; log2\; +\; ...\; +\; logn1))\; =\; O((n1+n2)log(n1+n2)\; -\; n1logn1)$

第二组加入序列：

$O((n1+n2+n3)log(n1+n2+n3)-(n1+n2)log(n1+n2))O((n1+n2+n3)log(n1+n2+n3)\; -\; (n1+n2)log(n1+n2))$ 刚好消除前一项

所以，对于第x组序列，总复杂度：

$O((n1+n2+\mathrm{.}\mathrm{.}\mathrm{.}+nx)log(n1+n2+\mathrm{.}\mathrm{.}\mathrm{.}+nx)-n1logn1)O((n1+n2+...+nx)log(n1+n2+...+nx)\; -\; n1logn1)$

随便算算，最后附上代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class mid_heap
{
public:
    void init(int val1, int val2)
    {
        if(val1 > val2) swap(val1, val2);

        lower_mid_heap.push_back(val1);
        upper_mid_heap.push_back(val2);
    }
   
    void push(int val)
    {
        if(val <= upper_mid_heap.front())
        {
            lower_mid_heap.push_back(val);
            push_heap(lower_mid_heap.begin(), lower_mid_heap.end());
        }
        else
        {
            upper_mid_heap.push_back(val);
            push_heap(upper_mid_heap.begin(), upper_mid_heap.end(), greater<int>());
        }

        if(lower_mid_heap.size() > upper_mid_heap.size() + 1)
        {
            upper_mid_heap.push_back(lower_mid_heap.front());
            push_heap(upper_mid_heap.begin(), upper_mid_heap.end(), greater<int>());

            pop_heap(lower_mid_heap.begin(), lower_mid_heap.end());
            lower_mid_heap.pop_back();
        }
        else if(upper_mid_heap.size() > lower_mid_heap.size() + 1)
        {
            lower_mid_heap.push_back(upper_mid_heap.front());
            push_heap(lower_mid_heap.begin(), lower_mid_heap.end());

            pop_heap(upper_mid_heap.begin(), upper_mid_heap.end(), greater<int>());
            upper_mid_heap.pop_back();
        }
    }

    int get() const
    {
        return lower_mid_heap.size() > upper_mid_heap.size() ? lower_mid_heap.front() : upper_mid_heap.front();
    }

private:
    vector<int> lower_mid_heap, upper_mid_heap;
};


int main() 
{
    int n1;
    cin >> n1;

    int num1, num2;
    mid_heap heap;
    if(n1 == 1)
    {
        cin >> num1;
        cout << num1 << endl;
    }
    else
    {
        cin >> num1 >> num2;
        heap.init(num1, num2);
        for(int i = 2; i < n1; i ++)
        {
            cin >> num1;
            heap.push(num1);
        }
        cout << heap.get() << endl;
    }

    int n2;
    while(cin >> n2)
    {
        for(int i = 0; i < n2; i++)
        {
            cin >> num1;
            heap.push(num1);
        }
        cout << heap.get() << endl;
    }
}