BZOJ 2957 楼房重建

作者: MayFlyyh 分类: 线段树 发布时间: 2018-09-18 18:12 ė 6 没有评论

> 小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

> 为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

> 施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。在第i天,建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

> 输入格式:
第一行两个正整数N,M

> 接下来M行,每行两个正整数Xi,Yi

> 输出格式:
M行,第i行一个整数表示第i天过后小A能看到的楼房有多少栋

。。一开始以为是要维护函数

首先算出每个最高点与原点所组成直线的斜率。显然能且只能看见的个数是斜率组成的最长上升子序列的长度。

该题就变成了动态维护最长上升子序列

考虑该题个数具有可加性,考虑线段树维护

对于每个区间,把原点看作是该区间的最左边,cnt[x]表示以x左端点为原点,该区间能看到的个数,max[x]表示该区间最高的高度

这样带来一个不错的性质,就是我们可以正解继承线段树左儿子的数据。

从而在算右儿子的时候也要重新计算,递归下去的复杂度是nlog^2^(n)

考虑,如果左区间的最高高度小于右区间左儿子最高高度,那显然右区间右儿子的数量可以全部继承 (应该是cnt[x]-cnt[x<<1],如果直接读cnt[x<<1|1]相当于把右区间右儿子当作原点了,就不对了),然后把左区间的最高高度带进右区间左儿子再计算就好。(因为右区间左儿子不是原点了 如果左区间的最高高度小于右区间左儿子的最高高度,那显然右区间左儿子贡献为0,然后计算右区间右儿子即可。 ``` #include
const int N = 120000;
double max[N<<2]; int cnt[N<<2]; int n,m; int calc(int cur,int l,int r,double v){ if(l==r) return v>1;
if(max[cur<<1]>=v){
return cnt[cur]-cnt[cur<<1]+calc(cur<<1,l,mid,v); } else{ return calc(cur<<1|1,mid+1,r,v); } } void modify(int cur,int l,int r,int x,double v){ if(l==r){cnt[cur]=1;max[cur]=v;return ;} int mid=l+r>>1;
if(x<=mid) modify(cur<<1,l,mid,x,v); else modify(cur<<1|1,mid+1,r,x,v); max[cur]=std::max(max[cur<<1],max[cur<<1|1]); cnt[cur]=cnt[cur<<1]+calc(cur<<1|1,mid+1,r,max[cur<<1]); } int main(){ scanf("%d %d",&n,&m); while(m--){ int x,y; scanf("%d %d",&x,&y); modify(1,1,n,x,(y*1.0/x)); printf("%d\n",cnt[1]); } return 0; } ```

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/339

发表评论

电子邮件地址不会被公开。

Ɣ回顶部