总览：
类似 f i = a i × b j + c i + d j f_i=a_i\times b_j+c_i+d_jfi=ai×bj+ci+dj 的式子
因为存在 a i × b j a_i\times b_jai×bj 项，所以不能单调队列优化
转化成 d j = − a i × b j + f i − c i d_j=-a_i\times b_j+f_i-c_idj=−ai×bj+fi−ci
类似于 y = k x + b y=kx+by=kx+b，维护凸包
其中 k kk 为 − a i -a_i−ai，b bb 为 f i − c i f_i-c_ifi−ci，凸包上的点 ( x , y ) (x,y)(x,y) 为 ( b j , d j ) (b_j,d_j)(bj,dj)
最大化截距 b bb，维护上凸包
版权声明：本文为hongkongreporter原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。