记一下。
形如 \(f_i=\min/\max\{f_j+a_ib_j+c_i+d_j+e\}\) 的式子可以使用斜率优化。
如果斜率有单调性，可以使用单调队列。
如果没有，可以使用李超树或者 cdq 分治。
单调队列暂鸽。
没有单调性，使用李超树。
为方便记录，只讨论 \(f_i=\min\{f_j+a_ib_j+c_i+d_j+e\}\)，\(\max\) 同理。
对式子变形一下：
\[\begin{aligned} f_i&=\min\{f_j+a_ib_j+c_i+d_j+e\}\\ &=\min\{b_ja_i+f_j+d_j\}+c_i+e\\ \end{aligned} \]把 \(b_ja_i+f_j+d_j\) 看作是 \(y=kx+b\) 的形式，也就是每一次往李超树里塞一条 \(k=b_j,b=f_j+d_j\) 的直线，查询的时候只需要查在 \(x=a_i\) 的最值就行了。
cdq 的话还没学。
标签：min,斜率,cdq,相关,ib,优化,单调,李超树 From： https://www.cnblogs.com/osfly/p/17774232.html