主题

主题

 
   

2957: 楼房重建

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=2957

Description

  小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

  为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

  施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。在第i天,建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建,也可以比原来小---拆除,甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

Input

  第一行两个正整数N,M

  接下来M行,每行两个正整数Xi,Yi

Output

  M行,第i行一个整数表示第i天过后小A能看到的楼房有多少栋

Sample Input

3 4

2 4

3 6

1 1000000000

1 1

Sample Output

1

1

1

2

数据约定

  对于所有的数据1<=Xi<=N,1<=Yi<=10^9N,M<=100000


个人解法:

我觉得这个题挺棒的,不管是我自己瞎YY的naive算法还是线段树的做法。

后来去看了题解,发现也有人和我想的差不多……

我的想法是分块。

首先显然,我们把每个点的斜率拿出来,那么问题转换为求序列中有多少个很像localmaxima数的玩意(即前面没有比它大或者相等的数字)。

每个块维护从头开始的最长上升序列L[i]。不在这个L[i]序列里面的自然不可能是localmaxima。

修改只需要暴力重构块。

查询,我们从第一个块开始,二分查找当前L[i]中大于当前最大值的有多少个数字,然后更新当前的最大值。

通过调整块的大小,使时间复杂度均衡在O(msqrt(nlogn))。


代码如下:

https://code.csdn.net/snippets/2217938


挺巧妙的是这道题的分块不是平常的套路,什么维护桶啊或者维护排好序的数组啊啥的。维护一个没有见过的东西,挺锻炼思维的(当然也可能是我做题甚少比较naive)。


另一种线段树的解法:

思想差不多,不过线段树是拆分出了logn个线段,比分块的sqrt(n)少了一个log。也挺好的。

比方说Hzwer的博客里有涉及:

http://hzwer.com/6746.html

 
 
评论