Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 2957 楼房重建

小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<bits/stdc++.h>
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<max[cur];
    int mid=l+r>>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;
}
本文链接:http://www.mayflyyh.com/archives/339
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      线段树      BZOJ 2957 楼房重建
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ 2957 楼房重建
小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。 为了简化问题,我们考虑…
扫描二维码继续阅读
2018-09-18