共计 930 个字符，预计需要花费 3 分钟才能阅读完成。
使用的就是分块思想，之前写过总结，所以不再赘述；代码如下：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<cstring>
using namespace std;
const int maxn=100010;
const int sqrN=316;
stack<int>st;
int block[sqrN];
int table[maxn];
void peekMedian(int K){
int sum=0;
int idx=0;
while(sum+block[idx]<K){
sum+=block[idx++];
}
int num=idx*sqrN;
while(sum+table[num]<K){
sum+=table[num++];
}
printf(“%d\n”,num);
}
void push(int x){
st.push(x);
block[x/sqrN]++;
table[x]++;
}
void pop(){
int x=st.top();
st.pop();
block[x/sqrN]–;
table[x]–;
printf(“%d\n”,x);
}
int main(){
int x,query;
memset(block,0,sizeof(block));
memset(table,0,sizeof(table));
char cmd[20];
scanf(“%d”,&query);
for(int i=0;i<query;i++){
scanf(“%s”,cmd);
if(strcmp(cmd,”Push”)==0){
scanf(“%d”,&x);
push(x);
}else if(strcmp(cmd,”Pop”)==0){
if(st.empty()==true){
printf(“Invalid\n”);
}else{
pop();
}
}else{
if(st.empty()==true){
printf(“Invalid\n”);
}else{
int K=st.size();
if(K%2==1)
K=(K+1)/2;
else
K=K/2;
peekMedian(K);
}
}
}
system(“pause”);
return 0;
}
