AcWing 1543. 栈
原题链接
中等
作者:
sy123
,
2021-01-03 23:03:40
,
所有人可见
,
阅读 489
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int tr[N];
stack<int> s;
int lowbit(int i){
return i&(-i);
}
void add(int x,int v){
for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;
}
int getsum(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void Peekmedian(){
int left=1,right=N,mid,k=(s.size()+1)/2;
while(left<right){
mid=left+right>>1;
if(getsum(mid)>=k)right=mid;
else left=mid+1;
}
cout<<left<<endl;
}
int main(){
int n;
char str[20];
cin>>n;
while(n--){
scanf("%s",str);
if(strcmp(str,"Push")==0){
int x;
scanf("%d",&x);
s.push(x);
add(x,1);
}
else if(strcmp(str,"Pop")==0){
if(s.empty()){
cout<<"Invalid"<<endl;
}
else{
cout<<s.top()<<endl;
add(s.top(),-1);
s.pop();
}
}
else if(strcmp(str,"PeekMedian")==0){
if(s.empty()){
cout<<"Invalid"<<endl;
}
else{
Peekmedian();
}
}
}
return 0;
}