https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805053695574016
输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e6+10,M=4004;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
stack<LL> st;
vector<LL> v;
vector<LL>::iterator it;
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
if(s=="Pop")
{
//当栈中没有元素的时候就是非法的，
//否则输出我们抛出的那个元素并且与此同时在vector中删除一个一样的
if(st.size()==0) cout<<"Invalid"<<endl;
else
{
cout<<st.top()<<endl;
it=lower_bound(v.begin(),v.end(),st.top());
v.erase(it);//it表示的是指针位置
st.pop();
}
}
else if(s=="PeekMedian")
{
//当栈中没有元素的时候属于非法操作，
//否则因为vector下标后退直接-1/2输出即可
if(st.size()==0) cout<<"Invalid"<<endl;
else cout<<v[(st.size()-1)/2]<<endl;
}
else
{
LL x;
cin>>x;
st.push(x);
it=lower_bound(v.begin(),v.end(),x);
v.insert(it,x);//在vector中it的位置直接插入x这个元素（保持vector的递增性）
}
}
}
return 0;
}