A

给定N个形如$f_i(x)=a_i*x^2+b_i*x$的二次函数

有Q次询问每次给出一个$x$,求$max{f_i(x)}$

再菜也只是菜这么一两天了

过了这几天,奥赛就与我无关了

可能退役之前最后一篇?

观察到二次函数没有c

二次函数可以转化成$x(a*x+b)$

就可以分类讨论了,分成$x>0,x<0$

只讨论$>0$($<0$同理)

$>0$时按照$a$升序,$b$升序排序

排序后,对于每一个值域预处理,回答时$O1$

假设值域上两个值$x,x+1$

$x$取到最大值为$mxid$,那么$x+1$取到最大值一定大于等于$mxid$

证明

$(x+1)*a+b=x*a+b+a$

$a$排序后是单调递增的

因为$mxid$之前a都$<=a_{mxid}$,本来就$<=mxid$现在增加量$<=mxid$

所以可以链表乱搞

复杂度$O(值域ln(值域))$

复杂度证明

经过去重之后

假设最后一个值为$a_{mxid},b_{mxid}$

极限情况就是一直跳$a_1$,最大是$a_1$

会跳多少次解不等式

$a_{lst}*x*x+b_{lst}*x>a_1*x*x+b_1*x$

假设x>0

$a_{lst}*x+b_{lst}>a_1*x+b_1$

于是有了

$x>frac{b_1-b_{lst}}{a_{lst}-a_1}$

然后设分母为$delta_a$

仍然考虑极限情况$delta_a$为$6e4$,

$b_1-b_{lst}=6e4$

n每次减少1

于是复杂度就是$frac{6e4}{6e4}frac{6e4}{6e4-1},,,,,frac{6e4}{1}$

调和级数$O(值域ln(值域))$