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

分析:

首先明确问题,对于每栋楼房的斜率K=H/X,问题就是问有多少个楼房的K比前面所有楼房的K都要大。

这题树套树当然可以,但是挺麻烦的,本渣觉得最简单就是分块……

将N个楼房分成T块,不断维护每个块内楼房的可视序列,如一个块内楼房的高度分别为(3 1 4 2 6 7)那么这个块内楼房的可视序列就是(3 4 6 7)(注意不同的块内是不干扰的,如第一个块可视序列为(3 4 6),第二块的序列可以是(5 7 8))

对于每个修改,我们只需对每个块内的楼房暴力维护可视序列就行了,O(N/T)

对于每个询问,我们只需一个块一个块看,不断维护到目前为止的可视序列中K的最大值kmax(不在可视序列内的楼房的K值一定不大),那么对于查询每个块的时候,可以二分可视序列找到第一个大于kmax的位置,若没有则这个块的所有楼房都不可见,如果存在,那么这个位置后的此块中的可视序列楼房都能看见,那么就更新答案和kmax,不断往后做

注意:毕竟时间比较紧,所以常数还是尽可能写小点,二分和max函数还是自己写好些,不然会爆RP……

05-11 20:11