HDU 4967 Handling the Past

第一次分塊，第一次自己想到分塊 覺得開心~~(灑花

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<cmath>
using namespace std;
typedef struct _op{
    int type;
    int num;
    int stamp;
}OP;
typedef struct _sts{
    OP ops[230];
    int a[230];
    int ptr;
    int cnt;
    bool isupdate;
}status;
status block[230];
OP ops[50005];
int dd = 230;
inline void clear_status(int ind){
    //printf("dd = %d\n", dd);
    block[ind].ptr = 0;
    block[ind].cnt = 0;
    block[ind].isupdate = false;
    for(int lx = 0;lx < dd;lx++)
        block[ind].ops[lx].type = -1;
    return;
}
int _step = 0;
void update_status(int ind){
    block[ind].ptr = 0;
    block[ind].cnt = 0;
    block[ind].isupdate = true;
    for(int lx = 0;lx < dd;lx++){
        //_step++;
        //if(_step >= 10000000) printf("%d\n", 1/0);
        if(block[ind].ops[lx].type == -1) continue;
        //printf("a\n");
        OP& op = block[ind].ops[lx];
        if(op.type == 0){
            block[ind].a[block[ind].cnt++] = op.num;
        }else if(op.type == 1){
            if(block[ind].cnt <= 0)
                block[ind].ptr--;
            else
                block[ind].cnt--;
        }
    }
    return;
}
/*void print_status(int ind){
    printf("----------------------------------\n");
    printf("block: %d\n",ind);
    printf("ptr = %d\n", block[ind].ptr);
    printf("nums: ");
    for(int lx = 0;lx < block[ind].cnt;lx++)
        printf("%d ", block[ind].a[lx]);
    printf("\n");
    printf("ops: \n");
    for(int lx  = 0;lx < dd;lx++){
        if(block[ind].ops[lx].type == -1) continue;
        printf("at %d: %d\n", lx, ops[lx].type);
    }
    printf("----------------------------------\n");
    return;
}*/
/*void assertR(bool c){
    if(c == false)
        printf("%d\n", 1/0);
    return;
}*/
int tmp[230];
int peak(int t){
    int b = t/dd, bb = t%dd;
    int ptr = 0, cnt = 0;
    for(int lx = 0;lx < bb;lx++){
        //assertT(lx < 230);
        const OP& op = block[b].ops[lx];
        if(op.type == -1) continue;
        if(op.type == 0){
            tmp[cnt++] = op.num;
        }else if(op.type == 1){
            if(cnt > 0)
                cnt--;
            else
                ptr--;
        }
    }
    if(cnt > 0) return tmp[cnt-1];
    ptr--;
    for(b--; b >=0 ; b--){
        if(block[b].isupdate == false)
            update_status(b);
        ptr += block[b].cnt;
        if(ptr >= 0) return block[b].a[ptr];
        ptr += block[b].ptr;
    }
    return -1;
}
int timearr[50005], timecnt;
int main()
{int n;_step = 0;int ccc = 0;for(;;){
    timecnt = 0;
    ccc++;
    scanf("%d", &n);
    if(n == 0) break;
    dd = (int)(sqrt(n+1));
    //printf("block width %d\n", dd);
    for(int lx = 0;lx <= n/dd;lx++)
        clear_status(lx);
    for(int lx = 0;lx < n;lx++){
        char tp[10];scanf("%s", tp);
        if(tp[1] == 'u'){ //push
            int a;scanf("%d", &a);
            ops[lx].type = 0, ops[lx].num = a;
        }else if(tp[1] == 'o'){ //pop
            ops[lx].type = 1;
        }else if(tp[1] == 'e'){ //peak
            ops[lx].type = 2;
        }/*else
            printf("%d\n", 1/0);*/
        int t; scanf("%d", &t);
        timearr[timecnt++] = t;
        ops[lx].stamp = t;
    }
    sort(timearr, timearr+timecnt);

    for(int lx = 0;lx < n;lx++)
        ops[lx].stamp = lower_bound(timearr,timearr+timecnt, ops[lx].stamp) - timearr;
    printf("Case #%d:\n", ccc);
    _step += n*dd;
    for(int lx = 0;lx < n;lx++){
        /*printf("oping at tie %d:", ops[lx].stamp);
        if(ops[lx].type == 0){
            printf("push %d\n", ops[lx].num);
        }else if(ops[lx].type == 1){
            printf("pop\n");
        }else
            printf("peak\n");*/
        if(ops[lx].type == 2){
            printf("%d\n", peak(ops[lx].stamp));
        }else{
            block[ops[lx].stamp/dd].ops[ops[lx].stamp%dd] = ops[lx];
            block[ops[lx].stamp/dd].isupdate = false;
        }
        //update_status(ops[lx].stamp/dd);
        //print_status(ops[lx].stamp/dd);
    }
}return 0;}