L3-002 特殊堆栈 (30 分)

题目描述：

维护一个栈，三种操作

• push x,塞x入栈
• pop，如果没有数，就Invalid,否则弹栈顶，并输出
• PeekMedian,输出栈中的中值

给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。

思路：

用从小到大排序的vector的insert和erase来维护

对于push x，我们去lower_bound(x),用迭代器it来记录，insert(it, x)

对于pop,我们同样的，去二分x，删掉就行

对于求中值，因为vector是排好序的，所以直接输出中间的那个就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
vector<int>v;
vector<int>::iterator it;
string s;
stack<int>st;
void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> s;
        if(s[1] == 'o'){//pop
            if(st.empty())cout << "Invalid\n";
            else{
                int x = st.top();
                cout << x << endl;
                st.pop();
                it = lower_bound(v.begin(), v.end(), x);
                v.erase(it);
            }
        }
        else if(s[1] == 'u'){//push
            cin >> x;
            st.push(x);
            it = lower_bound(v.begin(), v.end(), x);
            v.insert(it, x);
        }
        else{//mid
            if(st.empty())cout << "Invalid\n";
            else{
                if(v.size() % 2 == 0)cout << v[v.size() / 2 - 1] << endl;
                else cout << v[v.size() / 2] << endl;
            }
        }
    }
}


int main(){
    io;
    work();
    return 0;
}