用哈希，把push的数x作为下标给hashTable（实则不存在，直接用tree树状数组记录数据）+1，pop则是以最后一个数x作为下标-1 。
树状数组和其原理不再赘述，需要注意的是最后的二分搜索（实则是lower_bound）中位数。
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map>#define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 100010 #define MAX (1<<30)+1 #define V vector<int>using namespace std;int tree[LEN];int lowbit(int x){return x&-x; }int getSum(int p){int sum=0;while(p>0){sum+=tree[p];p-=lowbit(p);}return sum; }void update(int p,int x){while(p<LEN){ //对于有确定边界的树状数组，应该是 p<=N ，但是这题不用考虑这些 tree[p] +=x;p+=lowbit(p);} }char buf[100]; stack<int> s;void PeekMedian(){int l=1,r=LEN,mid,k=(s.size()+1)/2;while(l<r){mid=(l+r)/2;if(getSum(mid)<k){l=mid+1;}else{r=mid;}}O("%d\n",l); }int main(){ // freopen("1057.txt","r",stdin);int N,t;I("%d",&N);while(N--){I("%s",buf);if(strcmp(buf,"Pop")==0){if(s.empty()) puts("Invalid");else{t=s.top();O("%d\n",t);s.pop();update(t,-1);}}else if(strcmp(buf,"Push")==0){I("%d",&t);update(t,1);s.push(t);}else{if(s.empty()) puts("Invalid");else PeekMedian();}}return 0; }
