题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805417945710592
题意：对一个栈进行push， pop和找中位数三种操作。
思路：
好久没写题。感觉傻逼题写多了稍微有点数据结构的都不会写了。
pop和push操作就不说了。
找中位数的话就二分去找某一个数前面一共有多少小于他的数，找到那个小于他的数刚好等于一半的。
找的过程中要用到前缀和，所以自然而然就应该上树状数组。
要注意树状数组的界应该是1e5而不是当前数的最大值。
//#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x7f7f7f7f using namespace std;
const int maxn = 1e5 + ;
int n, size;
int sum[maxn];
stack<int>sss;
int small = , big = 1e5; void add(int x, int val)
{
while(x < 1e5){
sum[x] += val;
x += (x & -x);
}
} int query(int x)
{
int ans = ;
while(x){
ans += sum[x];
x -= (x & -x);
}
return ans;
} int main()
{
scanf("%d", &n); while(n--){
string op;
cin>>op;
if(op == "Push"){
int key;
cin>>key;
sss.push(key);
//small = min(small, key);
//big = max(big, key);
add(key, );
}
else if(op == "Pop"){
if(sss.size() == ){
printf("Invalid\n");
}
else{
add(sss.top(), -);
printf("%d\n", sss.top());
sss.pop();
}
}
else if(op == "PeekMedian"){
if(sss.size() == ){
printf("Invalid\n");
}
else{
int st = small, ed = big;
int ans = ;
while(st <= ed){
int mid = (st + ed) / ;
size = sss.size();
int res = query(mid);
if(res < (size + ) / ){
st = mid + ;
}
else{
ans = mid;
ed = mid - ;
}
}
printf("%d\n", ans);
}
}
} return ;
}
