楼房重建 – 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;
}