李超线段树
李超线段树
—— 维护多个一次函数单点最值的数据结构
基本算法
李超线段树本质上是一个标记永久化的线段树，对于插入的一条线段 $(x_0,y_0),(x_1,y_1)$，我们在区间 $[x_0,x_1]$ 上进行修改：
- 如果线段树上该点还没有线段，直接赋值。
- 如果原线段树上储存线段的中点值比该线段小，那么交换两条线段，这是保证两端只会有一段使得加入的线段比原线段更优。
- 判断哪边插入线段更优，递归继续讨论哪边。
于是，我们就插入完了一条线段。关于时间复杂度，我们首先会把一条线段分成 $\log$ 份往下递归，然后每次递归最深能够达到 $\log$ 次，因此一次插入线段是 $\log^2$ 的。但是对于直线，我们不需要分成 $\log$ 份的操作，因此复杂度为单 $\log$。
对于一次查询操作，我们能够一路递归下去，然后取所有线段在 $x$ 的值的 $\max$。之所以要一路取 $\max$，是因为我们在存的根节点的线段只是中点最大的线段，但是对于所有的它不一定最大，因此一路往上取 $\max$ 即可。
对于大部分题目，我们只需要掌握直线的李超线段树即可，因为在优化动态规划的时候基本都是全局的，但也不乏 恶心 的出题人出一些只能用李超线段树解决的线段问题，因此在写直线李超线段树的同时，也不要忘记复习线段。
Warning
对于一些卡精度的题目，在比较大小的时候需要引入 $eps$。具体来说，它的值取很趋近于 $0$ 的小数，一般为 $10^{-8}$ 或 $10^{-9}$，我们认为，所有 $\operatorname{abs}(x-a)<eps$ 的值都等于 $x$，也即 $x$ 的邻域 $U(x,eps)$ 都等于 $x$。这是因为有的时候，因为精度问题，
C++里面的double会把 $3.14$ 取成 $3.1400000001$ 或者 $3.1399999999$，因此加上才可万无一失。对于加上 $eps$ 的不等式，我们有以下规定：
$$a\le b\Leftrightarrow a<b+eps$$
$$a\ge b\Leftrightarrow a>b-eps$$
$$a<b\Leftrightarrow a<b-eps$$
$$a>b\Leftrightarrow a>b+eps$$于是我们在解决问题的时候就可以规避精度问题。
李超线段树的初始化非常魔怔，大部分时候我们只需要将它置 $0$，但对于有些题目，求最大最小值的时候，我们最好把所有的 $b$ 赋值成 $\pm \infty$ 来确保它不会使得原来最大小于 $0$ 的变成 $0$，最小大于 $0$ 的等于 $0$。
关键代码
线段插入
1 | void update(int p,int l,int r,int left,int right,line g){ |
直线插入
1 | void update(int p,int l,int r,line f){ |
查询
1 | int query(int p,int l,int r,int x){ |
可以发现 李超线段树比线段树真的短很多！！！
进阶
动态开点
类似于动态开点的线段树，李超线段树也可以动态开点，在合并线段树或者定义域特别大的时候尤为重要，其实它的算法过程和普通线段树差不多，在普通的李超线段树的 update 里面加上 if(!p) p=++idx;，在 query 里面加上 if(!p) return INF; 即可。值得注意的是，在动态开点的时候总需要两个数组 ls 和 rs 分别记录左儿子和右儿子的编号。
合并李超线段树
同样地，类似于合并线段树，基于动态开点李超线段树上，我们在有一边为空的时候直接返回另一端，在两边都不为空的时候我们两边分别递归下去进行更新，在更新的时候一定要注意，我们需要把需要合并的 t[q] 直线放进去给 p 更新线段来取最大值，因为李超线段树无法简单合并，需要不断更新，容易得到复杂度方程 $O(n)=n\log n+O(\frac{n}{2})$，但是我不会算，大概估测 $O(n\log^2 n)$ 吧。
1 | int merge(int p,int q,int l,int r){ |
题目讲解
CF1303G Sum of Prefix Sums 题解
Description
给定一棵树和点权值 $a_i$，求树上的一个路径 $(u,v)$ 使最大化
$$\sum\limits_{i=u}^v\sum_{j=u}^i a_i$$
注意这里 $(u,v)$ 编号不一定连续，只需是树上路径即可。
Solution
首先是树上的路径问题，容易想到使用点分治来解决问题。我们分治路径经过的点 $root$，然后找它里面所有的路径进行匹配。
如果进行这个思路，我们就需要首先了解将一条路径分成两个要如何计算。
对于一条路径 $(u,v)$，设共经过了点 $p_1,p_2,\dots,p_n$，显然，根据题目中给出的式子，有：
$$val=\sum\limits_{i=1}^n i\times a_i$$
假设它经过了中间点 $p_m$，即路径分为了 $p_1,p_2,\dots,p_m$ 和 $p_{m+1},p_{m+2},\dots,p_n$，那么计 $val1=\sum\limits_{i=1}^m i\times a_i,val2=\sum\limits_{i=m+1}^n (i-m)\times a_i,s=\sum\limits_{i=m+1}^n a_i$，那么显然有整个式子的值为：
$$val=val1+val2+s\times m$$
也就是说，我们要拿这个式子对所有经过 $root$ 的路径来进行匹配。注意到式子中有 $s\times m$ 这一项，这里 $s$ 与后一段路径相关，$m$ 和前一段路径相关，因此很容易想到一次函数的形式，考虑使用李超线段树维护。
推理到这里，我们就不难写出算法流程：
- 找到一个子树的重心进行点分治。
- 找到以它为根节点的子树中所有一个端点是它的路径。
- 将这些路径进行匹配，这期间使用李超线段树。
- 继续遍历它的儿子找到重心，继续步骤1。
因为这个题也不是板子，我也不讲点分治和李超树的详细过程了。复杂度点分治有一个 $\log$，李超线段树维护直线也有一个 $n\log n$，因此总复杂度在 $n\log^2n$。
此外，本题有一些值得注意的点：
- 在寻找路径的时候，注意到点权不为负，因此显然最优解在叶子结点上，因此只需要记录叶子结点到根节点的路径即可。
- 在计算子树大小和各个节点的父亲的时候，注意一定不要胡来给 $root$ 一个父亲，或者将它的父亲设成当前的根节点，因为在求 $dep$ 的时候会爆掉 (Wa on test 32)。
- 在匹配的时候，需要正着反着都来一遍，因为显然 $(u,v)$ 和 $(v,u)$ 这两条路径的权值是不一样的。
其它的就问题不大了。
Main Code
1 |
|
P5504 [JSOI2011] 柠檬
Description
给定 $n$ 个整数 $x_i$，要求把这些整数不重不漏地划分成若干个小段，并给每个小段一个常数 $x_0$ 那么这个小段的贡献就是 $x_0\times s_{x_0}^2$，其中 $s_{x_0}$ 是指 $x_0$ 在这段区间中出现的次数。
Solution
首先，一个很重要的结论是对于第 $i$ 个位置，转移过来的决策点显然需要满足 $x_i=x_j$，否则考虑从 $x_{j+1}$ 转移过来反而可以多一个 $x_j$ 的贡献。
于是，我们计 $s_i$ 表示第 $i$ 个位置是 $x_i$ 第 $s_i$ 次出现，并且设 $f_i$ 表示分到 $i$ 的最大价值，不难得到方程：
$$f_i=f_{j-1}+x_i\times (s_i-s_{j-1})^2$$
化简之后得到：
$$f_i=f_{j-1}+x_i\times s_i^2+x_i\times s_{j-1}^2-2\times x_i\times s_{i}\times s_{j-1}$$
但是注意到这里同时与 $i,j$ 相关的既包含 $s_j$ 项又包含 $s_j^2$ 项，显然不可做。但是我们发现这里的 $x_i$ 完全是个幌子。我们已经得出决策点 $j$ 与 $i$ 满足 $x_i=x_j$，那么我们不妨计 $x_i$ 为常数 $c$，于是方程就变成了：
$$f_i=f_{j-1}+cs_i^2+cs_{j-1}^2-2cs_is_{j-1}$$
移项后得到：
$$f_{j-1}+cs_{j-1}^2=2cs_is_{j-1}+f_i-cs_i^2$$
直接套李超线段树或者单调栈的板子即可。但是注意，这里对于每个值，我们都需要一个李超线段树来维护，因此这里需要 $10^4$ 棵李超线段树，为了不 $\text{MLE}$，需要动态开点的李超线段树。
P2497 [SDOI2012] 基站建设
Description
给定一条直线上的一些点，通过 $x_i,r_i,v_i$ 来表示这个点的信息，分别表示它的横坐标，以它为切点的圆的半径以及使用它的代价。我们要求第一个点必须被使用，并且如果我们要使用第 $i$ 个点，必须找到一个点 $j$ 使得 $j<i$，并且要以 $i$ 为切点做一个与横坐标轴相切的圆使得它与第 $j$ 个圆相切，计这个圆的半径为 $r_i’$，那么需要额外花费 $\sqrt{r_i’}$ 的代价。求这些点的圆能够到达 $s$ 的最小代价。其中到达 $s$ 被定义为 $\exist i$ 使得 $\operatorname{abs}(s-x_i)\le r_i$。
Solution
我们先假设我们已经知道了 $r_i’$，来推动态规划方程。设 $f_i$ 表示选第 $i$ 个点的最小代价，不难得到转移方程：
$$f_i=\min\limits_{j=1}^{i-1}{f_j+\sqrt{r_i’}+v_i}$$
我们需要计算出 $r_i’$ 到底是多少来判断它怎么转移，于是我们先画一张图：
通过几何关系，不难得到一个直角三角形，在这个三角形里使用勾股定理，得到：
$$(x_i-x_j)^2+(r’_i-r_j)^2=(r_i+r_j)^2$$
展开并消除两边 $r_i’^2$ 和 $r_j^2$ 项之后，得到：
$$r_i’=\frac{(x_i-x_j)^2}{4r_j}$$
回带到方程式中，得到：
$$f_i=\min\limits_{j=1}^{i-1}{f_j+\sqrt{\frac{(x_i-x_j)^2}{4r_j}}+v_i}=\min\limits_{j=1}^{i-1}{f_j+\frac{x_i-x_j}{2\sqrt{r_j}}+v_i}$$
于是我们计 $g_i=\frac{1}{2\sqrt{r_i}}$，式子就变成：
$$f_i=f_j+x_ig_j-x_jg_j+v_i$$
移项得到：
$$f_i-v_i=x_ig_j+f_j-x_jg_j$$
使用李超线段树维护即可。注意本题需要离散化。