CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====李超树=====
<del>大家都知道，李超树最近很火，究竟是为什么很火呢？李超树到底是什么梗？相信大家对李超树都很熟悉，李超树就是我们每天都会经常遇到的，但是李超树是怎么回事呢？就由小编来为大家介绍一下。</del>

简单来说就是维护线段的线段树，基本上有三个用途：
  - 维护区间的多条直线
  - 单点查询直线中最值
  - 区间查询最值

具体操作大致是对单个区间分配编号，记录每个区间是否有优势线段以及优势线段的值。

更新时和普通线段树思想几乎一致，如果左右两端都高于当前优势曲线，就直接在当前区间更新，如果有交点就是普通线段树的更新过程啦。

几点性质：
  - 标记永久化
  - 修改的时间复杂度是$(log n)^2$
  - 实际上就是在维护一个凸包


放题：[[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3547|UVA 1106 Machine Works]]
（维护一次函数最大值）
（正解貌似是斜率优化+cdq QAQ）

CVBB ACM Team

用户工具

站点工具

页面工具