BZOJ2957:楼房重建 分块

逗逼分块,写完题解结果被吞QoQ.直接贴代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*fS=buf,*fT=buf;
        if(fS==fT){fT=(fS=buf)+fread(buf,1,L,stdin);if(fS==fT)return EOF;}
        return*fS++;
    }
    inline bool digit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void Get(T&x){
        int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[600010],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 100010
int begin[510],end[510],bel[N];
 
double res[N];
 
struct Stack{
    int top;
    double s[510];
    Stack():top(0){}
    inline void upd(int l,int r){
        top=0;
        for(int i=l;i<=r;++i)if(!top||res[i]>s[top])s[++top]=res[i];
    }
    inline int getans(const f2&x){
        if(!top||s[top]<=x)return 0;
        int L=1,R=top,mid;
        while(L<R){
            mid=(L+R)>>1;
            if(s[mid]>x)R=mid;else L=mid+1;
        }return top-L+1;
    }
}S[510];
 
int main(){
    int n,m;Fio::Get(n),Fio::Get(m);register int i,j;
 
    int persize=sqrt(n),nums=0;
    for(i=1;i*persize<=n;++i)begin[++nums]=(i-1)*persize+1,end[nums]=i*persize;
    if(n%persize)++nums,begin[nums]=(nums-1)*persize+1,end[nums]=n;
    for(i=1;i<=nums;++i)for(j=begin[i];j<=end[i];++j)bel[j]=i;
 
    for(i=1;i<=n;++i)res[i]=0;
 
    int x,y,ret;f2 Max;
    while(m--){
        Fio::Get(x),Fio::Get(y);
        res[x]=(f2)y/x;
        S[bel[x]].upd(begin[bel[x]],end[bel[x]]);
        for(ret=0,Max=0,i=1;i<=nums;++i){
            ret+=S[i].getans(Max);
            if(S[i].top&&S[i].s[S[i].top]>Max)Max=S[i].s[S[i].top];
        }
        Fio::print(ret);
    }
 
    return Fio::final(),0;
}