CF1710B Rain 解题报告
有 n 天在下雨,每一天,雨会在第 x_i 个地方降落,降雨量为 p_i.降雨量会累加,对于一个地方 j,它的总降雨量为 a_j,每一次降雨其能接收到的降雨量为 \max(0,p_i-|x_i-j|) .
一个地方为发大水的定义为:在任何时间段有 a_j > m .
你需要求出:对于每一天,独立地将该天的降雨量撤销之后,这一天是否还有地方是发大水的.
n \leq 2\times 10^5,p_i \leq 10^9,m \leq 10^9
以下称第 i 天降雨的位置 x_i 为关键点 i.
首先观察到一个性质:我们只需要对每个降雨的 x_i 讨论是否发大水.
简略证明:
我们可以