P1485 火枪打怪

发布时间 2023-10-23 16:06:41作者: 御坂夏铃

二分 \(p\),因为只能溅射到左边,所以从右往左打,但 \(O(n^2\log(n+m)))\) 显然过不去。对于能溅射到位置 \(j\) 的子弹,拆式子:

\[\sum p-(i_x-j)^2 \]

\[\sum p-i_x^2+2\times i_x\times j-j^2 \]

\[tot\times(p-j^2)-\left(\sum i_x^2\right)+2\times j\times\sum i_x \]

因为每次 check 溅射的范围是一样的,所以只需双指针维护当前怪物向后定长区间内的子弹数量、威力值和、威力值平方和即可。