堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。

输入格式：

输入的第一行是正整数 N（≤105\le 10^5）。随后 N 行，每行给出一句指令，为以下 3 种之一：

Push key
Pop
PeekMedian

其中 key 是不超过 10510^5 的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。

输出格式：

对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。

输入样例：

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
作者
陈越
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

如题所示：
正解：线段树or树状数组；
刚开始想这题想不明白该怎么使用数据结构来解决，然后看了一个大佬树状数组的题解，观察到本题是一个类似于桶排序的方法来解决，由于线段树能维护具有可加性的数据，因为此题范围[1,1e5]那么建树就利用的是每个整数值在序列中出现的次数，二分查找[1,mid]区间出现次数，即可求解；
代码如下：


/*************************************************************************
    > File Name: pta.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年11月26日 星期四 15时19分09秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 1e6+10,inf = 1e5;
int sum[N];
int n,tot,now[N/10];char op[99];
void add(int s,int t,int k,int y,int p){
    int mid = (s+t)>>1;
    if(s==k&&t==k){
        sum[p] += y;
        return;
    }
    if(mid>=k){
        add(s,mid,k,y,p<<1);
    }
    else add(mid+1,t,k,y,p<<1|1);
    sum[p] = sum[p<<1]+sum[p<<1|1];
    return;
}
int found(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r){
        return sum[p];
    }
    int ans = 0,mid = (s+t)>>1;
    if(l<=mid)ans += found(l,r,s,mid,p<<1);
    if(r>mid)ans += found(l,r,mid+1,t,p<<1|1);
    return ans ;
}int mx = -1;
int getans(int x){
    int l = 1,r = mx ;
    int sum = 0;
    while(l<r){
        int mid = (l+r)>>1;
        sum = found(1,mid,1,inf,1);
        if(sum>=x) r = mid;
        else l = mid + 1;
    }
    return l;
}
void solve(){
    scanf("%d",&n);
    while(n--){
        scanf("%s",op);
        if(op[0] == 'P'&&op[1] == 'o'){
            if(!tot)puts("Invalid");
            else {
                add(1,inf,now[tot--],-1,1);
                printf("%d\n",now[tot+1]);
            }
        }
        else if(op[1]=='u'){
            scanf("%d",&now[++tot]);
            mx = max(mx,now[tot]);
            add(1,inf,now[tot],1,1);
        }
        else {
            if(!tot){
                puts("Invalid");continue;
            }
            int t = (tot+1)>>1;
            printf("%d\n",getans(t));
        }
    }
    return;
}
int main(){
    solve();
    return 0;
}

这个建树是我没想到的，当初的想法想到了或许建树时建1e5个节点，最初设为0；而类似桶排序的思路则是网上树状数组题解提供给我的。这个题感觉是二分答案？二分答案类的题目现在有点不敢想，因为二分答案大多数范围都很大，但其实仔细一想，就多了一个log复杂度，当正向想不出答案时，不妨利用逆向思维，在答案这个集合中进行考虑；

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章