题意：中文题意。

思路：因为所有数<=1e5，权值线段树维护每个数出现多少次，然后每次出栈入栈都更新权值就好了。

好久没写线段树了，写的好爽233。

1 #include 
     
       2 using namespace std; 3 #define N 100010 4 #define lson rt<<1, l, m 5 #define rson rt<<1|1, m + 1, r 6 int tree[N<<2], val[N]; 7 stack
      
        sta; 8  9 void pushup(int rt) { tree[rt] = tree[rt<<1] + tree[rt<<1|1]; }10 11 void update(int rt, int l, int r, int id, int val) {12     if(l == r && l == id) { tree[rt] += val; return ; }13     if(l == r) return ;14     int m = (l + r) >> 1;15     if(id <= m) update(lson, id, val);16     else update(rson, id, val);17     pushup(rt);18 }19 20 int query(int rt, int l, int r, int id) {21     if(l == r) return l;22     int m = (l + r) >> 1;23     if(tree[rt<<1] >= id) return query(lson, id);24     else return query(rson, id - tree[rt<<1]);25 }26 27 int main() {28     int n; scanf("%d", &n);29     char s[20]; int x, now; int ma = 100000;30     for(int i = 1; i <= n; i++) {31         scanf("%s", s);32         if(s[1] == 'o') {33             if(sta.empty()) { puts("Invalid"); continue; }34             now = sta.top(); sta.pop();35             update(1, 1, ma, now, -1);36             printf("%d\n", now);37         } else if(s[1] == 'e') {38             if(sta.empty()) { puts("Invalid"); continue; }39             now = query(1, 1, ma, (sta.size() + 1) / 2);40             printf("%d\n", now);41         } else {42             scanf("%d", &x);43             sta.push(x);44             update(1, 1, ma, x, 1);45         }46     }47     return 0;48 }