【李超线段树应用】【斜率优化】

李超树可以用于维护斜率优化。

斜率优化的维护

一般来说，斜率优化有三种维护方式：

1. 维护凸包
   对于状态转移方程：\(f(i)=A(i)B(j)+C(i)+D(j)\)
   可以写成：\(D(j)=-A(i)B(j)+f(i)-C(i)\)
   把所有的决策点\(j\)，计作二维平面坐标上的一个点\((-B(j),D(j))\),则求对于以\(A(i)\)为斜率的直线，代入某个决策点后，使得截距取的最值的决策点即为\(f(i)\)的最值
   若求的是最小值，则维护下凸包；最大值则维护上凸包。
   维护方式：
   若查询的斜率或插入的点的横坐标具有单调性的话，首先考虑单调栈和单调队列（代码，复杂度，常数，都要比其他方法好）。
   否则，用平衡树维护（一般用set）
2. 李超树维护
   对于状态转移方程：\(f(i)=A(i)B(j)+C(i)+D(j)\)
   可以写成：\(f(i)-C(i)=B(j)A(i)+D(j)\)
   所以想要求\(f(i)\)的最值，实际上就是对于每条\(k=B(j)\),\(b=D(j)\)的直线，求在\(x=A(i)\)处的极值，显然可以用李超树来维护。
   当然还要满足所查询的\(A(i)\)不应过大。
   复杂度只有一个log，原因是插入的是直线。
   例题
3. 离线用cdq分治。