算法下 P405 分块思想

//https://pintia.cn/problem-sets/994805342720868352/problems/994805417945710592
//算法下 P405 分块思想
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 10e5+10;
const int sqrN = 316; //sqrt(100001)  表示块内个数

stack<int> st; //栈
int block[sqrN]; //记录每一块中存在的元素个数
int table[maxn];    //hash数组，记录元素当前存在个数


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,"PeekMedian") == 0){
            if(st.empty()){
                printf("Invalid\n");
            }else{
                int K = st.size();
                if(K % 2 == 1) K = (K+1)/2;
                else K = K/2;
                peekMedian(K);
            }
        }else{
            if(st.empty()){
                printf("Invalid\n");
            }else{
                Pop();
            }
        }
    }

    return 0;
}