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 |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| - 维护区间的多条直线 | - 维护区间的多条直线 | ||
| - 单点查询直线中最值 | - 单点查询直线中最值 | ||
| - | - 区间查询 | + | - 区间查询最值 |
| + | |||
| + | 具体操作大致是对单个区间分配编号，记录每个区间是否有优势线段以及优势线段的值。 | ||
| + | |||
| + | 更新时和普通线段树思想几乎一致，如果左右两端都高于当前优势曲线，就直接在当前区间更新，如果有交点就是普通线段树的更新过程啦。 | ||
| 几点性质： | 几点性质： | ||
| - 标记永久化 | - 标记永久化 | ||
| - 修改的时间复杂度是$(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]] | ||
| 行 15: | 行 21: | ||
| （正解貌似是斜率优化+cdq QAQ） | （正解貌似是斜率优化+cdq QAQ） | ||
| - | <del>那么以上就是今天小编为大家整理的关于李超树是什么梗，李超树为什么火的原因。如果大家喜欢，可以点赞表示对小编的支持。欢迎在下方评论和小编一起讨论喔</del> | + | |
2020-2021/teams/farmer_john/bazoka13/cg_segment_tree.1588933579.txt.gz · 最后更改: 2020/05/08 18:26 由 bazoka13
