【PAT甲级】1057 Stack (30 分)（分块）

题意：

输入一个正整数N（<=1e5），接着输入N行字符串，模拟栈的操作，非入栈操作时输出中位数。（总数为偶数时输入偏小的）

trick：

分块操作节约时间

AAAAAccepted code：

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
string s;
stack<int>sk;
int num[100007],block[1007];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int _size=sqrt(100005);
    for(int i=1;i<=n;++i){
        cin>>s;
        if(s[1]=='u'){
            int x;
            cin>>x;
            sk.push(x);
            ++num[x];
            ++block[x/_size];
        }
        else if(s[1]=='o')
            if(sk.empty())
                cout<<"Invalid
";
            else{
                int x=sk.top();
                sk.pop();
                cout<<x<<"
";
                --num[x];
                --block[x/_size];
            }
        else
            if(sk.empty())
                cout<<"Invalid
";
            else{
                int mid=sk.size()/2;
                if(sk.size()&1)
                    ++mid;
                int sum=0;
                int k;
                for(k=0;k<=_size&&sum+block[k]<mid;++k)
                    sum+=block[k];
                for(int j=k*_size;j<(k+1)*_size;++j){
                    sum+=num[j];
                    if(sum>=mid){
                        cout<<j<<"
";
                        break;
                    }
                }
            }
    }
    return 0;
}