首页 > 代码库 > BZOJ 2957 楼房重建
BZOJ 2957 楼房重建
2957: 楼房重建
Description
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
Input
第一行两个正整数N,M
接下来M行，每行两个正整数Xi,Yi
Output
M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋
Sample Input
2 4
3 6
1 1000000000
1 1
Sample Output
1
1
2
对于所有的数据1<=Xi<=N，1<=Yi<=10^9，N,M<=100000
Source
中国国家队清华集训 2012-2013 第一天
原以为不过是道水题，是道线段树裸题。不就是个长度为n的序列，m个操作，每个操作单点修改（delta=y*1.0/x，斜率）然后询问root罢了。
不用pushdown，但是update确实让人很迷。我最开始以为自己的update是O（lg n）的，但最后居然成了O（n）的（逻辑不严谨）。啊啊啊啊啊！
注意到题目要求，nd->sum=nd->ls->sum+find(nd->rs,nd->ls->max);原来居然还存了一段线段的min值，结果发现并不需要。find(nd,val)指一段线段中比val大的能看见的总数。递归分解，若nd->ls->max<=nd，那么左边就注定为0了，再去find（nd->rs,val）。否则右边没有影响，则return nd->num-nd->ls->num+find（nd->ls,val），这样就可以保证每次范围减半，就是O（lg n）的。
代码如下：
1 /************************************************************** 2 Problem: 2957 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1424 ms 7 Memory:4732 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 template<class T>inline void readin(T &res) {15 static char ch;T flag=1;16 while((ch=getchar())<‘0‘||ch>‘9‘)if(ch==‘-‘)flag=-1;17 res=ch-48;while((ch=getchar())>=‘0‘&&ch<=‘9‘)res=(res<<1)+(res<<3)+ch-48;res*=flag;18 }19 20 const int N = 100100;21 struct Node {22 double max;23 int num;Node *ls, *rs;24 }pool[N<<1], *tail=pool, *root;25 26 Node *build(int lf,int rg) {27 Node *nd=tail++;28 if(lf==rg) {29 nd->max=nd->num=0;30 } else {31 int mid=(lf+rg)>>1;32 nd->ls=build(lf,mid);33 nd->rs=build(mid+1,rg);34 nd->max=nd->num=0;35 }36 return nd;37 }38 int find(Node *nd,int lf,int rg,double delta) {39 if(lf==rg) {40 return nd->max>delta;41 }42 int mid=(lf+rg)>>1, ans=0;43 if(nd->ls->max<=delta) return find(nd->rs,mid+1,rg,delta);44 return nd->num-nd->ls->num+find(nd->ls,lf,mid,delta);45 }46 void modify(Node *nd,int lf,int rg,int pos,double delta) {47 if(lf==rg) {48 nd->max=delta;49 nd->num=1;return ;50 }51 int mid=(lf+rg)>>1;52 if(pos<=mid) modify(nd->ls,lf,mid,pos,delta);53 else modify(nd->rs,mid+1,rg,pos,delta);54 nd->num=nd->ls->num+find(nd->rs,mid+1,rg,nd->ls->max), nd->max=std::max(nd->ls->max,nd->rs->max);55 }56 57 int main() {58 int n, m, x, y;59 readin(n);readin(m);60 root=build(1,n);61 for( int i = 1; i <= m; i++ ) {62 readin(x);readin(y);63 modify(root,1,n,x,y*1.0/x);64 printf("%d\n",root->num);65 }66 return 0;67 }
不过，天算不如人算。没有想到，居然可以直接上暴力！当然，前提是要分块。每一次把修楼点所属的块暴力重构。这是有策略的，扫一遍保证单调性，是O（sqrt（n））的，之前做O（sqrt（n）log n）便会TLE。之后枚举每个块，upper_bound之前的最大值，加上并更新最值，而这是O（sqrt（n）log n）的。
我用vector来存块，因为不熟悉，所以卡了很久。调试时间比线段树久，但确实是不可多得的绝佳经历。
代码如下（似乎比线段树短）：
1 /************************************************************** 2 Problem: 2957 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:4052 ms 7 Memory:3976 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 #include <vector>14 template<class T>inline void readin(T &res) {15 static char ch;T flag=1;16 while((ch=getchar())<‘0‘||ch>‘9‘)if(ch==‘-‘)flag=-1;17 res=ch-48;while((ch=getchar())>=‘0‘&&ch<=‘9‘)res=(res<<1)+(res<<3)+ch-48;res*=flag;18 }19 const int N = 100100;20 int belong[N], pos, bound, num[N], tnum;21 double aa[N], tmp;22 std::vector<double> bb[N];23 int main() {24 int n, m, S, x, y;25 readin(n);readin(m);26 S=(int)floor(sqrt(n*log(n)/log(2)/2));27 pos=1-S;for( int i = 1; i <= n; i++ ) {28 belong[i]=pos;29 if(i-pos>=S) pos=i, num[i]=++tnum, belong[i]=pos;30 }31 for( int i = 1; i <= m; i++ ) {32 readin(x);readin(y);33 aa[x]=y*1.0/x;34 bound=std::min(belong[x]+S-1,n);35 tmp=0;bb[num[belong[x]]].clear();for( int i = belong[x]; i <= bound; i++ ) if(aa[i]>tmp) bb[num[belong[x]]].push_back(aa[i]),tmp=aa[i];36 tmp=0;int ans=0;37 for( int i = 1; i <= tnum; i++ ) {38 bound=bb[i].size()-1;39 pos=std::upper_bound(bb[i].begin(),bb[i].end(),tmp)-bb[i].begin();40 ans+=bound+1-pos;41 if(bound>=0) tmp=std::max(tmp,bb[i][bound]);42 }43 printf("%d\n",ans);44 }45 return 0;46 }
恩。最后讨论一下速度。似乎暴力只慢了3倍左右。
| 线段树 | 4732 kb | 1424 ms | 1523 B |
| 暴力分块+vector+upper_bound | 3976 kb | 4052 ms | 1232 B |
BZOJ 2957 楼房重建