PAT甲级-1057 Stack (30分)【转载/树状数组】

点击链接PAT甲级-AC全解汇总

原文转自：
李小白~：1057 Stack (30分)
李小白~：树状数组（简单介绍）

其他：
柳婼：【数据结构】树状数组笔记
柳婼：1057. Stack (30)-PAT甲级真题（树状数组）
Uncle_Sugar：1057. Stack (30)五种解法总结（大杂烩）

非科班出身，这太难了，头秃

我的代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int c[maxn]={
    0};//记录出现的次数
stack<int> sta;
int lowbit(int m){
    return m&(-m);}
int getSum(int m)//返回出现的次数
{
    int cnt = 0;while(m > 0){
    cnt += c[m];m -= lowbit(m);}return cnt;
}
void update(int x, int v)//更新出现的次数
{
    while(x <= maxn){
    c[x] += v;x += lowbit(x);}
}
int peekMedian()
{
    int left=1,right=maxn,k=(sta.size()+1)/2;while(left < right){
    int mid=(left + right)/2;if(getSum(mid) >= k)right=mid;else left=mid+1;}return left;
}
int main()
{
    fill(c, c+maxn, 0);int N;cin>>N;for(int i=0; i<N; i++){
    string str;cin>>str;if(str=="Pop"){
    if(sta.empty())printf("Invalid\n");else{
    printf("%d\n", sta.top());update(sta.top(), -1);//出现次数-1sta.pop();}}else if(str=="PeekMedian"){
    if(sta.empty())printf("Invalid\n");else printf("%d\n", peekMedian());}else if(str=="Push"){
    int t;scanf("%d", &t);sta.push(t);update(t, 1);//出现次数+1}}return 0;
}