noip 模拟 草堆

很巧妙的一道题

首先发现一个火焰高度的区间贡献为一个分段一次函数

也就是可以写成 \(a*t+b\) 的形式

Q ：为什么分段呢

A ： 因为要考虑左右两边比它高的火焰，前面限制它，后面吞并它

询问实际上是求前缀的差值

那我们可以把 \([L,R]\) 转换成 询问区间 \([1,L-1]\) 和 \([1,R]\)

对于一个询问 \([1,R']\)

假设覆盖 \(R'\) 点的火焰编号为 \(i\)

那么我们只需要知道 \([1,i-1]\) 的函数截距和斜率的 \(sum\) 就好了

首先解决第一个问题

找到某一时刻覆盖某一点的火焰编号

其实就是询问一个区间的最大值

第二个问题

我们只需要在每一时刻维护出截距和斜率的前缀和就好了

函数的断点查找比较麻烦

Code