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