李超线段树是一种按照值域维护一次函数最值的数据结构,其核心在于一次函数和值域的双单调性。
如果预先对于值域离散也可以维护其最值。
也就是说只要满足时一次函数,以及下标的单调性都可以利用李超线段树维护。
李超线段树就是利用线段树来维护一次函数的最值,每一个结点对应了一个区间 \([l, r]\)。
我们定义一个区间 \([l, r]\) 的最优函数 \(kx + b\) 为在 \(\lfloor \frac{l + r}2 \rfloor\) 处为最值的函数。
最优函数满足在中点是最值,但是不一定满足在端点是最值,所以需要分为左右两个区间判断。
然而对于一次函数来说,如果满足时最优函数,那么对于另一条函数,只能有左半或者右半是优于它的:
于是更新有三种情况:
- 如果当前函数优于原函数,那么交换,进行下面的判断
- 如果当前函数在左端点优于原函数,那么递归更新左区间
- 如果当前函数在右端点优于原函数,那么递归更新右区间
注意到如果满足的最优函数,那么不存在一条两边都大于它的函数,此时至多进入一个区间,根据线段树有 \(O(\log n)\) 层,所以更新的复杂度是 \(O(\log n)\) 的。
单点查询的时候需要注意,需要利用经过的每一个节点的最优函数来更新答案,这样一定是不劣的。
那么如果这个一次函数限定了值域,那么意味着这个函数只能更新部分的区间。
那么考虑到线段树本身可以将一个区间拆分为 \(O(\log n)\) 个区间,然后我们对于这些区间用此函数来更新即可。可以做到 \(O(\log^2 n)\) 维护区间函数最值。
板子题 李超线段树 我就不细说了。
这里说说如何利用李超线段树优化 DP。
能用斜率优化的 DP 都可以使用李超树维护,并且一般都可以过( \(10^7\) 也不是不可以,只是需要大力卡常而已)
式子形如:\(f_i = \max f_j + c_i \times c_j\)。
此时我们将 \(c_j\) 看作 \(k\), \(f_j\) 看作 \(b\),那么问题转化为有一堆 \(y = kx + b\),现在给定 \(x = c_i\),求最值。
如果 \(c_i\) 的值域很小,可以支持 \(O(V \log V)\) 的时间和 \(O(V)\) 的空间,那么十分简单,直接利用李超线段树维护即可。
但是如果 \(c_i\) 不连续,但是观察到一共有 \(O(n)\) 个 \(c_i\),于是考虑离散化,排序后将它们映射到 \([1, n]\) 的整数上,考虑下标是单调的,那么李超线段树所依赖的最优函数的性质任然成立,所以可以 \(O(n \log n)\) 的维护这颗李超线段树了。
但是接下来如果我们限制了转移的区间:\(f_i = \max_{i - k \le j \lt i} f_j + c_i \times c_j\)。
首先,如果 \(c_i\) 是单调的,那么是简单的,这意味着离散化后 \(i \to c_i\) 意味着下标和值域是匹配的,所以可以利用区间维护最优函数来做,这样复杂度是 \(O(n \log^2 n)\) 的。
如果 \(c_i\) 是不单调的,那么这题就太阴间了 QwQ,但是任然可以利用李超线段树解决。
利用线段树分治,维护支持撤销的一棵李超线段树,然后在 DP 的过程中边求答案边更新分治线段树即可,这样复杂度也是 \(O(n \log^2 n)\) 的。
标签:log,线段,李超,区间,31,最值,函数 From: https://www.cnblogs.com/jeefy/p/17777443.html