【分块】bzoj2957 楼房重建

http://www.cnblogs.com/wmrv587/p/3843681.html

ORZ 分块大爷。思路很神奇也很清晰。

把块内最值和块内有序两种良好的性质结合起来，非常棒地解决了这个问题。

图中黑色的楼房即为每个块内的“可视序列”，显而易见，在块内它们的K（斜率）是单增的。

由于上图中第一个块的maxK比后面两个块的maxK都要大，所以后两个块对答案没有贡献，这也是显然的。这就是维护maxK的意义所在。

否则，若一个块可以更新maxK的话，则其中的部分楼房是“可见的”，具体来说，就是在那个比之前的maxK要大的楼房的后面的在可视序列中的楼房数。<---请从方链接看原版题解。

另外，并不会像他说的，基本不会T，如果把块大小开得合适。

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<cstring>

 using namespace std;

 inline double max(const double &a,const double &b){return a>b?a:b;}

 vector<double>See[];

 double k[];

 int sz,sum,l[],r[],num[],n,m,x,y;

 double maxv[];

 int Res,Num;char C,CH[];

 inline int G()

 {

     Res=;C='*';

     while(C<''||C>'')C=getchar();

     while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}

     return Res;

 }

 inline void P(int x)

 {

     Num=;if(!x){putchar('');puts("");return;}

     while(x>)CH[++Num]=x%,x/=;

     while(Num)putchar(CH[Num--]+);

     puts("");

 }

 void makeblock()

 {

     memset(maxv,,sizeof(maxv));

     sz=sqrt((double)n*1.05);

     for(sum=;sum*sz<n;sum++)

       {

         l[sum]=(sum-)*sz+;

         r[sum]=sum*sz;

         for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

       }

     l[sum]=sz*(sum-)+;

     r[sum]=n;

     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;

 }

 inline void update()

 {

     k[x]=(double)y/x;

     See[num[x]].clear();

     maxv[num[x]]=0.0;

     for(int i=l[num[x]];i<=r[num[x]];i++)

       if(k[i]>maxv[num[x]])

         {

           maxv[num[x]]=k[i];

           See[num[x]].push_back(k[i]);

         }

 }

 inline void query()

 {

     int ans=;double tmp=0.0;

     for(int i=;i<=sum;i++)

       if(!See[i].empty())

         {

             ans+=See[i].end()-upper_bound(See[i].begin(),See[i].end(),tmp);

             tmp=max(tmp,maxv[i]);

         }

     P(ans);

 }

 int main()

 {

     n=G();m=G();makeblock();

     for(int i=;i<=m;i++){x=G();y=G();update();query();}

     return ;

 }

巴特西

【分块】bzoj2957 楼房重建

最新文章

热门文章