首页 > 编程语言 >算法学习笔记(31): 李超线段树

算法学习笔记(31): 李超线段树

时间:2023-10-20 16:51:02浏览次数:47  
标签:log 线段 李超 区间 31 最值 函数

李超线段树是一种按照值域维护一次函数最值的数据结构,其核心在于一次函数和值域的双单调性。

如果预先对于值域离散也可以维护其最值。

也就是说只要满足时一次函数,以及下标的单调性都可以利用李超线段树维护。

李超线段树就是利用线段树来维护一次函数的最值,每一个结点对应了一个区间 \([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

相关文章

  • Vivado生成bitstream时报错[Opt 31-67] Problem: A LUT3 cell in the design is missi
    这个原因主要是因为有一个引脚没有用到,解决方法。1、打开Schematic。2、根据提示的模块去找,比如说我的报错。[Opt31-67]Problem:ALUT3cellinthedesignismissingaconnectiononinputpinI1,whichisusedbytheLUTequation.Thispinhaseitherbeenleftun......
  • 音视频技术开发周刊 | 313
    每周一期,纵览音视频技术领域的干货。UC伯克利脑机接口新突破!利用脑电波即可复现歌曲,语言障碍者有福了脑机接口领域再添一笔,凭借大脑电波波形图,可逆向重建歌曲。文字解码以外的又一重大突破!特斯拉「擎天柱」机器人视频爆了!端到端AI大脑加持,挑战高难度瑜伽特斯拉人形机器人「擎天柱」......
  • 20231018 NOIP 模拟赛
    时间安排7:50~8:00看题,只会A。8:00~8:10写完A。8:10~9:00推式子+写40pts,少乘了一个\(n-i+1\)调了半天。9:00~9:01看了一眼C的式子,猜一手结论。9:01~10:21觉得可以换根,写个暴力\(dp\)。10:09会了50pts,换下根就行了,10:21调出来了。10:21~10:50给B和C加......
  • 20231019
    20231019NOIP#24总结时间安排7:40~8:10看题,\(A,B,C\)各会一点,\(D\)没想法。8:10~8:30写\(A\)的暴力。8:30~9:00写\(C\)的暴力。9:00~9:30会\(A\)写了。9:30~11:00马上看出了\(B\)的做法,但是可能太久没写了写挂了,调了一个小时。11:00~11:40\(D\)写半天看......
  • [刷题笔记] [算法学习笔记]树上差分 -- Luogu P3128
    DescriptionProblem:https://www.luogu.com.cn/problem/P3128FJ给他的牛棚的\(N\)个隔间之间安装了\(N-1\)根管道,隔间编号从\(1\)到\(N\)。所有隔间都被管道连通了。FJ有\(K\)条运输牛奶的路线,第\(i\)条路线从隔间\(s_i\)运输到隔间\(t_i\)。一条运输路线会给......
  • 2023-2024-1 20231312 《计算机与程序设计》第四周学习总结
    作业信息这个作业属于哪个课程<班级的链接>2023-2024-1-计算机基础与程序设计|-这个作业要求在哪里<作业要求链接>2023-2024-1计算机基础与程序设计第四周作业|这个作业的目标《计算机基础概论》第4,5章《C语言程序设计》第3章|作业正文作业链接教材学......
  • 20231019打卡
    上午的课程是UML的序列图和协作图。在这门课上,我们学习了UML建模语言中的序列图和协作图,这是一种图形化的表示方法,用于描述对象间的交互和协作过程。通过老师的讲解和实践练习,我对序列图和协作图的概念和绘制规则有了更深入的理解。这种图形化的表达方式对于我们软件工程师来说非......
  • 231019校内赛
    T1机器人题解傻逼题,但是有人\(90\)分一开始十分想直接暴力\(2^n\)判断每一步选不选求出所有可能性但是会发现它有制约关系有些步走了之后,有些就必须走了所以需要用一个数组记录当前位置走没走过,或者是不是障碍注意走没走过不能直接赋值\(1,0\)因为回溯时会直接将前......
  • 20231018NOIP训练赛
    20231018NOIP训练赛时间安排7:50-8:10写T19:10-10:30写T210:30-11:50写T4总结没看T3去做了T4,考完试发现T3比T4更可做。题解T1贪心题,排序之后贪心即可T2对a做前缀和,把题目的式子化成\[\sum_{l=1}^{n}\sum_{r=l}^n\sum_{i=l}^{r}b[i]*(sum[r]-sum[l])\]对于每一个......
  • 231019校内赛
    T1购买饮料题解简单且傻逼的题目有人更傻逼没做出来很容易就会想去拿最后能喝多少瓶去做未知量来求然后就有一个严重的问题,它会赊账非常明显这样算是不得行的那么考虑换个思路以能喝多少套饮料为未知量,先除去第一套,免得一套都买不起时赊账买了饮料然后将剩余的钱除以\(......