解法一：树状数组

参考：https://blog.csdn.net/liuchuo/article/details/52231409

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
// 树状数组c对应的原数组a[i]表示i出现的频率
int c[MAX_N];
deque<int> s;
int lowbit(int x) {
    return x & (-x);
}
// 在i的位置上加上k
void update(int i, int k) {
    while (i < MAX_N) {
        c[i] += k;
        i += lowbit(i);
    }
}
// 原数组a[1]到a[i]的和
int getsum(int i) {
    int res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
int peek() {
    int left = 1;
    int right = MAX_N;
    int target = (s.size() + 1) / 2;
    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (getsum(mid) < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    int num;
    string op;
    for (int i = 0; i < N; ++i) {
        cin >> op;
        switch (op[1]) {
            case 'o':
                if (s.empty()) {
                    cout << "Invalid\n";
                } else {
                    cout << s.back() << "\n";
                    update(s.back(), -1);
                    s.pop_back();
                }
                break;
            case 'u':
                cin >> num;
                update(num, 1);
                s.push_back(num);
                break;
            default:
                if (s.empty()) {
                    cout << "Invalid\n";
                } else {
                    cout << peek() << "\n";
                }
        }
    }
}