2020-2021:teams:farmer_john:bazoka13:cg_segment_tree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:bazoka13:cg_segment_tree [2020/05/08 18:26] bazoka13 创建 |
2020-2021:teams:farmer_john:bazoka13:cg_segment_tree [2020/05/10 21:23] (当前版本) bazoka13 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | =====李超树===== | ||
| <del>大家都知道，李超树最近很火，究竟是为什么很火呢？李超树到底是什么梗？相信大家对李超树都很熟悉，李超树就是我们每天都会经常遇到的，但是李超树是怎么回事呢？就由小编来为大家介绍一下。</del> | <del>大家都知道，李超树最近很火，究竟是为什么很火呢？李超树到底是什么梗？相信大家对李超树都很熟悉，李超树就是我们每天都会经常遇到的，但是李超树是怎么回事呢？就由小编来为大家介绍一下。</del> | ||
| - | ===李超树=== | + | |
| 简单来说就是维护线段的线段树，基本上有三个用途： | 简单来说就是维护线段的线段树，基本上有三个用途： | ||
| - 维护区间的多条直线 | - 维护区间的多条直线 | ||
| - 单点查询直线中最值 | - 单点查询直线中最值 | ||
| - | - 区间查询 | + | - 区间查询最值 |
| + | |||
| + | 具体操作大致是对单个区间分配编号，记录每个区间是否有优势线段以及优势线段的值。 | ||
| + | |||
| + | 更新时和普通线段树思想几乎一致，如果左右两端都高于当前优势曲线，就直接在当前区间更新，如果有交点就是普通线段树的更新过程啦。 | ||
| 几点性质： | 几点性质： | ||
| - 标记永久化 | - 标记永久化 | ||
| - 修改的时间复杂度是$(log n)^2$ | - 修改的时间复杂度是$(log n)^2$ | ||
| + | - 实际上就是在维护一个凸包 | ||
| + | |||
| 放题：[[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3547|UVA 1106 Machine Works]] | 放题：[[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3547|UVA 1106 Machine Works]] | ||
| 行 14: | 行 21: | ||
| （正解貌似是斜率优化+cdq QAQ） | （正解貌似是斜率优化+cdq QAQ） | ||
| - | <del>那么以上就是今天小编为大家整理的关于李超树是什么梗，李超树为什么火的原因。如果大家喜欢，可以点赞表示对小编的支持。欢迎在下方评论和小编一起讨论喔</del> | + | |
2020-2021/teams/farmer_john/bazoka13/cg_segment_tree.1588933560.txt.gz · 最后更改: 2020/05/08 18:26 由 bazoka13
