这题比较困难的地方是需要动态输出中位数，针对这个需求，我们可以把数据分为上下两部分，上部分是一个小根堆保存 \(\frac {N} {2}\)个数据；下方是一个大根堆，如果N为偶数，那么保存\(\frac {N} {2}\)，如果N是奇数那么保存\(\frac {N} {2} + 1\)个数据。这样我们只需要维护好这两个数据结构，在输出中位数的时候，直接输出下方的大根堆堆顶元素即可。

维护堆
如果上部分数据比下部分数据多，那么就删除上方最小的数然后拿到下面来；如果下部分比上部分的个数+1多，那么就删除下方最大的元素，拿到上面去；由于是平衡二叉树，所以每删除和插入一个元素的时间复杂度为\( O(logn)\)。

由于c++的堆没有提供删除操作，所以对于这题，我们可以使用multiset这个数据结构，其内部实现也是平衡树，如果使用迭代器遍历输出的话，默认从小到大输出。

代码

#include<iostream>
#include<algorithm>
#include<set>
#include<stack>
#include<cstring>

using namespace std;

stack<int> s;
multiset<int> up,down;//默认从小到大排序;其内部实现是平衡二叉树，插入和删除的时间复杂度是O(logn)

void adjust(){
    while(up.size()>down.size()){//如果上面部分大于下面部分了
        down.insert(*up.begin());
        up.erase(up.begin());
    }

    while(down.size()>up.size()+1){//如果下面的部分多了
        auto k = down.end();
        k--;//注意end()-1才是最后一个元素
        up.insert(*k);
        down.erase(k);
    }
}

int main(){
    int n;
    cin>>n;
    char op[20] ;
    while(n--){
        scanf("%s",op);
        if(strcmp(op,"Push")==0){
            int x;
            scanf("%d",&x);
            s.push(x);
            //注意这里不能写down.empty();这样up会因为没有元素而访问了begin而报错
            if(up.empty()|| *up.begin()>x) down.insert(x);
            else up.insert(x);
            adjust();
        }else if(strcmp(op,"Pop")==0){
            if(s.empty()) puts("Invalid");
            else{
                int x = s.top();
                s.pop();
                auto t=down.end();
                t--;
                if(*t<x) up.erase(up.find(x));//注意要先find了之后再删，如果直接up.erase(x),则会删掉所有的x
                else down.erase(down.find(x));
                printf("%d\n",x);
                adjust();
            }
        }else{
            if(s.empty()) puts("Invalid");
            else{
                auto t = down.end();
                t--;
                printf("%d\n",*t);
            }
        }
    }

    return 0;
}