1.该题重点！主要是模拟栈操作，能够频繁读取栈中元素的中位数。
2.本题的中间三个测试点非常容易超时。
3.需要采用树状数组+二分法。
树状数组：能够在o(logn)的时间内进行对a[i]操作和统计a[0]+a[1]+a[2]+…a[i]的操作。
我们把a[i]记录为i的出现次数，那么统计sum=a[0]+a[1]+a[2]+…a[i]，就可以知道小于等于i的元素出现的次数。而PeekMedian操作中，是求n/2或者（n+1）/2的元素，即当sum等于n/2或者（n+1）/2时，i就是我们需要输出的元素
4.利用树状数组，能够快速统计sum，利用二分法，能够快速定位i。
5.后续优化：可以考虑采用一个数组实现stack的功能，int stack[N]; int stackTop=0;//既是栈顶元素在stack数组的位置，也是栈内元素的总个数，push操作：stack[++stackTop]=x, pop操作：stack[stackTop–].
Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:
Push key
Pop
PeekMedianwhere key is a positive integer no more than 105.
Output Specification:
For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.
Sample Input:
17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop
Sample Output:
Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid
AC代码：
[c language=”++”]
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
#define MAX_N 100001
int Tree[MAX_N];
inline int lowbit(int x)
{
return(x&-x);
}
void add(int x, int value)
{
for (int i = x; i < MAX_N; i += lowbit(i))
Tree[i] += value;
}
int get(int x)
{//获取0到x的数组总和
int sum = 0;
for (int i = x; i; i -= lowbit(i))
sum += Tree[i];
return sum;
}
int main(void)
{
int n;
cin >> n;
char action[11];
stack<int> sta;
int maxNum = INT_MIN;
int minNum = INT_MAX;
memset(Tree, 0, sizeof(Tree));
for (int i = 0; i < n; i++)
{
scanf("%s", action);
if (action[2] == ‘p’)
{//pop
if (sta.empty())
{
cout << "Invalid" << endl;
continue;
}
int top = sta.top();
sta.pop();
add(top, -1);//弹出，出现次数减1
printf("%d\n", top);
}
else if (action[2] == ‘e’)
{//PeekMedian
if (sta.empty())
{
cout << "Invalid" << endl;
continue;
}
int n = sta.size();//栈里的元素个数
int target = 0;
if (n % 2 == 0)
target = n / 2;
else
target = (n + 1) / 2;
//设中位数为i，用二分法查找
int l = 0;
int r = MAX_N – 1;
while (l <r – 1)
{
int mid = (l + r) / 2;
if (get(mid) < target)
l = mid;
else//如果get(mid)<=target，则r=mid，逐渐逼近
r = mid;
}
printf("%d\n", l + 1);
}
else
{//push
int tmp;
scanf("%d", &tmp);
sta.push(tmp);
maxNum = max(maxNum, tmp);
minNum = min(minNum, tmp);
add(tmp, 1);//弹出，出现次数加1
}
}
return 0;
}
[/c]