G – 楼房重建 (线段树)

  • 2019-02-06
  • 0
  • 0

题目链接:https://cn.vjudge.net/contest/281960#problem/G
题意:一个坐标轴,初始什么都没有,建筑工人每天会建一个高度为h的楼或者将x轴处的楼的高度改为h,输出每天后在(0,0)点可以看到多少个楼。
思路:肯定是线段树了,sum[rt]代表在(0,0)点看[l,r]这段区间可以看到多少个,问题就在怎么向上更新了。
首先sum[rt<<1]可以看到的sum[rt]也可以看到,因为区间由(l,mid)变为(l,r)这段区间对于左边部分并没有什么变化,右边的部分就发生变化了,因为右边部分的左边多了一部分楼,这时候就要利用线段树的二分性求[mid+1,r]在左边多出了[l,mid]后可以看到多少个楼。

再加一个线段树maxx表示斜率的最大值。 设[l,mid]斜率的最大值为val。

1.val>=maxx[mid](此mid非彼mid),说明左部分全被多出来的区间挡住了,只查询右边可以看到多少个就可以了。
2.va<maxx[mid],此时sum[l,r]中的[mid,r]部分没有变化,所以直接加上sum[rt]-sum[rt<<1],然后只查询左边就可以了。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;
int a[maxn],n,m,sum[maxn*4];
double maxx[maxn*4];

int cal(int rt,int l,int r,double val)
{
    if(l==r)return maxx[rt]>val;
    int mid=(l+r)>>1;
    if(val>=maxx[rt<<1])return cal(rt<<1|1,mid+1,r,val);
    else return sum[rt]-sum[rt<<1]+cal(rt<<1,l,mid,val); } void updata(int rt,int l,int r,int x,double val) { if(l==r) { maxx[rt]=val; sum[rt]=1; return; } int mid=(l+r)>>1;
    if(x<=mid)updata(rt<<1,l,mid,x,val);
    else updata(rt<<1|1,mid+1,r,x,val);
    maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
    sum[rt]=sum[rt<<1]+cal(rt<<1|1,mid+1,r,maxx[rt<<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 val=y*1.0/x;
        updata(1,1,n,x,val);
        cout<<sum[1]<<endl;
    }
    return 0;
}

评论

还没有任何评论,你来说两句吧