楼房重建 – HYSBZ 2957 – 线段树二分

来源: 楼房重建 – HYSBZ 2957 – Virtual Judge

题意:一个坐标轴,初始什么都没有,建筑工人每天会建一个高度为h的楼或者将x轴处的楼的高度改为h,输出每天后在(0,0)点可以看到多少个楼。
首先,后面的楼能不能被看见我们可以通过判断这栋楼前面有没有斜率(高/距离0点的水平距离)大于这栋楼的来判断。
题目要求每个步骤后一共能看见多少楼,所以用线段树维护一下,线段树维护的有两个东西,一个是区间斜率的最大值,另一个就是区间共能看见多少楼。每次操作后输出sum[0]也就是整段区间一共能看见多少楼。
重要的就是更新sum的过程了,当合并l,r两段区间时,可以确定的是l段能看见的数目是不用动的,但是r段内就不一定了,因为当l段内有较高的楼的时候可能会挡道r段内的部分楼,计算合并后r段能看见多少楼可以分为两种情况,一种是l段的最大值大于等于rl段的最大值,那么就只计算rr段就可以了(递归二分),否则rr段一定可以看见,所以只计算rl段就可以了(递归二分),最终的复杂度是log级的。
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

int n,m;

int a[maxn],sum[maxn*4];
double maxx[maxn*4];

int cal(int o,int l,int r,double v)
{
    if(l==r)
        return maxx[o]>v;
    int mid=(l+r)>>1;
    if(v>=maxx[o<<1])return cal(o<<1|1,mid+1,r,v);
    else return sum[o]-sum[o<<1]+cal(o<<1,l,mid,v);
}

void updata(int o,int l,int r,int x,double v)
{
    if(l==r)
    {
        maxx[o]=v;
        sum[o]=1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        updata(o<<1,l,mid,x,v);
    else updata(o<<1|1,mid+1,r,x,v);
    maxx[o]=max(maxx[o<<1],maxx[o<<1|1]);
    sum[o]=sum[o<<1]+cal(o<<1|1,mid+1,r,maxx[o<<1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        double v=y*1.0/x;
        updata(1,1,n,x,v);
        cout<<sum[1]<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注