OI康复训练 BZOJ2957 楼房重建

很有意思的一道题,看完题解还想了一小会才明白,不过代码很好写。

我们考虑一下,我们可以只看每栋楼的关于原点的斜率,只要一栋楼,其左侧没有斜率大于等于他的楼,那么他就是可见的。

我们考虑线段树,我们每个点维护两个量,ans代表只看这片区域最多可看见的楼的数量(是忽略这篇区域左侧对其影响的),然后maxn代表这篇区域里的最大斜率。

然后我们考虑修改。

每次都递归到树叶,然后我们考虑合并。当前区域为k,其左孩子为l,右孩子为r。maxn直接在l,r的maxn中取max即可。那么对于ans,我们考虑以下几个情况,第一种情况,l的maxn大于r的maxn,那么ans[k]就等于ans[l]。第二种情况,ans[k] 就等于左侧的ans,和右侧在左侧maxn限制下的可见楼房数。我们此时定义一个函数cal(int x,int l,int r,int lmt),来代表x区域在lmt限制条件下的可见楼层数。

我们再考虑这个函数。

如果对于x他的maxn[l] >= maxn[r] 那么就相当于在就l在lmt限制下的楼层数。如果manx[l] <= lmt 那么就相当于r在lmt限制下的楼层数。否则的话,证明lmt < maxn[l],那么右侧的限制完全来源于左侧的最高楼,而左侧一的一些楼会因为lmt的限制而无法被看到,那么就是  ans[k] – ans[l] + cal(l,lmt)。ans[k] – ans[l]即为r在k的大环境下可见的楼的数量,因为可见楼的斜率是单调递增的,请自行领会。

最后时间复杂度是N(logN)^2。

发表评论