1057 Stack

link

1. Fenwick Tree:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
# define LL long long
using namespace std;

const int maxn=100000+10;
stack<int> stk;
int fenwick[maxn];

void updatetree(int index, int val){
    while(index<=100001){
        fenwick[index]+=val;
        index+=(index&-index);
    }
}

int gettree(int index){
    int res=0;
    while(index>=1){
        res+=fenwick[index];
        index-=(index&-index);
    }
    return res;
}

int findmid(){
    int target=stk.size()%2==0?stk.size()/2:(stk.size()+1)/2;
    int left=1;
    int right=100001;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(gettree(mid)>=target){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return left;
}

int main(){
    int N;
    cin>>N;
    while(N--){
        string comm;
        cin>>comm;
        if(comm=="Pop"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int t=stk.top();
                stk.pop();
                printf("%d
",t-1);
                updatetree(t,-1);
            }
        }else if(comm=="PeekMedian"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int n=findmid();
                printf("%d
", n-1);
            }
        }else{
            int val;
            cin>>val;
            stk.push(val+1);
            updatetree(val+1,1);
        }
    }

    return 0;
}

2. 线段树：

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
# define LL long long
using namespace std;

const int maxn=100000+10;
stack<int> stk;

int seg[maxn<<2];

void update(int targetidx, int idx, int left, int right, int val){
    if(targetidx<left || targetidx>right) return;
    if(left==right){
        seg[idx]+=val;
        return;
    }
    int mid=left+(right-left)/2;
    update(targetidx,idx<<1,left,mid,val);
    update(targetidx,idx<<1|1,mid+1,right,val);
    seg[idx]=seg[idx<<1]+seg[idx<<1|1];
}


int query(int target, int idx, int left, int right){
    if(left==right) return left;
    int mid=left+(right-left)/2;
    if(target<=seg[idx<<1]){
        return query(target,idx<<1,left,mid);
    }
    return query(target-seg[idx<<1],idx<<1|1,mid+1,right);

}


int main(){
    int N;
    cin>>N;
    while(N--){
        string comm;
        cin>>comm;
        if(comm=="Pop"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int t=stk.top();
                stk.pop();
                printf("%d
",t-1);
                update(t,1,1,100001,-1);
            }
        }else if(comm=="PeekMedian"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int size=stk.size();
                int target=size%2==0?size/2:(size+1)/2;

                int res=query(target,1,1,100001);
                printf("%d
",res-1);
            }
        }else{
            int val;
            cin>>val;
            stk.push(val+1);
            update(val+1,1,1,100001,1);
        }
    }
    return 0;
}

3. 大顶堆，小顶堆

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
# define LL long long
using namespace std;

stack<int> stk;
multiset<int,greater<int>> m1;
multiset<int> m2;

int main(){
    int N;
    cin>>N;
    while(N--){
        string comm;
        cin>>comm;
        if(comm=="Pop"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int t=stk.top();
                stk.pop();
                printf("%d
",t);
                if(m1.find(t)!=m1.end()){
                    m1.erase(m1.find(t));
                    if(m1.size()<m2.size()){
                        int tmp=*m2.begin();
                        m2.erase(m2.begin());
                        m1.insert(tmp);
                    }
                }else{
                    m2.erase(m2.find(t));
                    if(m1.size()-m2.size()>1){
                        int tmp=*m1.begin();
                        m1.erase(m1.begin());
                        m2.insert(tmp);
                    }
                }
            }
        }else if(comm=="PeekMedian"){
            if(stk.empty()){
                printf("Invalid
");
            }else{
                int n=*m1.begin();
                printf("%d
",n);
            }
        }else{
            int val;
            cin>>val;
            stk.push(val);
            if(val<=*m1.begin()){
                m1.insert(val);
                if(m1.size()-m2.size()>1){
                    int tmp=*m1.begin();
                    m1.erase(m1.begin());
                    m2.insert(tmp);
                }
            }else{
                m2.insert(val);
                if(m1.size()<m2.size()){
                    int tmp=*m2.begin();
                    m2.erase(m2.begin());
                    m1.insert(tmp);
                }
            }
        }
    }
    return 0;
}