前情提要
主要是觉得斜率优化的时候推式子好麻烦，然后用 set 维护凸包也好麻烦（最讨厌这种 set 状物），然后就直接学李超树了，直接代替所有单调队列优化 DP。
李超树，就是支持加入直线，并且查询单点（整数点）下所有直线最值的数据结构。
大神讲得好简单啊。。懂了。
李超树
李超树应用了标记永久化的 trick，就是不设懒标记，也不使用 pushup(down) 维护标记。为了保证查询返回信息的正确性，只需要在往下搜的路径上累加前面所有的标记，只要保证这个标记不漏即可，每个点维护的就是这样一个标记，代表一个直线的编号。我们只需要保证能构造一种标记方法，使得每次查询的时候结果正确即可。
接下来讲解插入直线的情况，也就是斜率优化 DP 里最常见的情况。并且维护的是最大值。
考虑以下递归函数 \(modify(l,r,f)\)。\(l\)，\(r\) 代表递归区间，\(f\) 代表目前下传的直线编号。我们尝试使用直线 \(f\) 来更新 \(l\)，\(r\) 这个区间：
- 首先，如果该区间的没有被任何直线标记过，直接标记上，然后返回（如果你的李超树维护的时直线，只有第一次修改才会这样）。
对于接下来的情况，我假设目前这个区间标记的线段编号为 \(g\)。
- 如果 \(f(l) \ge g(l)\) 且 \(f(r) \ge g(r)\)，那么可以直接拿 \(f\) 更新掉这个区间的标记，返回即可。
否则我们钦定 \(g(mid) \ge f(mid)\)，如果不满足，直接交换 \(f\)，\(g\)。
-
如果 \(f(l) > g(l)\)，证明在区间 \([l,mid]\) 中 \(f\) 可能有大于 \(g\) 的部分，但是 \([mid + 1,r]\)，中不可能有，于是递归 \(modify(l,mid,f)\)，保留右子树和当前节点的标记不变。
-
如果 \(f(r) > g(r)\)，证明在区间 \([mid + 1,r]\) 中 \(f\) 可能有大于 \(g\) 的部分，但是 \([l,mid]\)，中不可能有，于是递归 \(modify(mid + 1,r,f)\)，保留左子树和当前节点的标记不变。
注意到上面的两个判定使用的是严格的大于号，于是最多只会递归一边，然后修改就是 \(\mathcal{O}(\log n)\) 的。
单点查询简单，直接一个点往下扫，路上会经过很多标记的线的编号，直接在这些线中找到使得查询位置值最大的那个就行。这样显然是正确的。
例题
等会更新。