斜率优化&李超树

WJChp · 2024-03-12 18:27:26 · 个人记录

斜率优化dp

1. 写出dp方程，并让其变为线性

其中可能需要对性质的重要分析（难点）

式子一般长这个样

2. 模板化的，分离变量

具体的，先忽略 min/max （其实相当于选择一个最优的 j_0 ）

把只与 j_0 相关的项放在一边，只与 i 相关的项放在另一边,既与 j_0 相关又与 i 相关的放在一起

其中设

（把 j 抽象成点 ( X(j),Y(j) ) , i 抽象成直线 K(i)x+B(i) ）

则

若 Kk(x)$ 递增/递减，可以用单调队列（在队尾的斜率不达标的直接弹走）

若不行但 X(j) 单调 用二分

都不行，李超树（通解）

李超树

1. 完全体

link

要求在平面直角坐标系下维护两个操作：

1. 加入一个一次函数，定义域为 [l,r] ；
2. 给定 k ，求定义域包含 k 的所有一次函数中，在 x=k 处取值最大的那个，如果有多个函数取值相同，选编号最小的。

warning 1

当线段垂直于 x 轴时，会出现除以零的情况。假设线段两端点分别为 (x,y_0 和 (x,y_1) ， y_0<y_1] ，则插入定义域为 [x,x] 的一次函数 f(x)=0\cdot x+y_1 。

思想

按照线段树解决区间问题的常见方法，给每个节点一个懒标记。每个节点 i 的懒标记都是一条线段，记为 g_i 。

修改

考虑插入一条线段 g ，考虑左右端点恰好与 g 相同的的区间。若该区间无标记，直接打上用该线段更新的标记。

如果该区间已经有标记了，由于标记难以合并，只能标记永久化，把标记下传。但是子节点也有自己的标记，也可能产生冲突，所以我们要递归下传标记。

设当前区间的中点为 m ，我们拿新线段 g 在中点处的值与原最优线段 f 在中点处的值作比较。

如果新线段 g 更优，则将 g 和 f 交换。那么现在考虑在中点处 g 不如 f 优的情况：

1. 若在左端点处 g 更优，那么 g 和 f 必然在左半区间中产生了交点， g 只有在左区间才可能优于 f ，递归到左儿子中进行下传；

2. 若在右端点处 g 更优，那么 g 和 f 必然在右半区间中产生了交点， g 只有在右区间才可能优于 f ，递归到右儿子中进行下传；

3. 若在左右端点处 f 都更优，那么 g 不可能成为答案，不需要继续下传。

除了这两种情况之外，还有一种情况是 g 和 f 刚好交于中点，在程序实现时可以归入中点处 g 不如 f 优的情况，结果会往 g 更优的一个端点进行递归下传。

最后将 f 作为当前区间的懒标记。

这样可以在 O(\log^2 n) 完成修改(一个线段最多分成 logn 个区间，每个修改最多 logn 次)

查询

如图所示，由于使用了标记永久化，懒标记并不等价于在区间中点处取值最大的线段。 因此在查询时，在包含 x 的所有线段树区间（不超过 O(log n) 个）的标记线段中取最值，得出最终答案。

code

warning 2

有时 x 的范围过大或不为整数 ( 货币兑换 ），无法直接作为下标，可以对其离散化之后再处理

2. only直线

这其实是更常见的一种情况，大部分题目(斜优)都对定义域没有要求。

当然，依然可以通过插入定义域为全体的线段来解决，但是太过于麻烦，这里提供一种简单，常数小的实现。

修改

1. 拿新线段 g 在中点处的值与原最优线段 f 在中点处的值作比较，决定要不要交换。
2. 若 g 的斜率大于 f 的斜率，在右儿子下传 g，否则在左儿子下传(可以由函数 g - f 的单调性得出)。

（还是可以看这个图理解，g 的斜率大于 f 的斜率）

这样可以在 O(logn) 的复杂度内解决

查询

直接以当前线段在 x 位置的值与左/右儿子其中之一的值取最大/最小值即可，复杂度 O(logn)

plus part李超树&斜优

对于李超树，不需要考虑单调性。但 i 与 j 的地位颠倒。

对于

分离 i 和 j ,但把 i 抽象成点 ( X(i),Y(i) ) , j 抽象成直线 k(j)x+b(j)

即

其中设

则有

每次在李超树里查询横坐标为 X(i) 的最大/小值，然后得到 f(i)=Y+g(i) ，再将 y=K(i)x+B(i) 插入即可