ChiFAN鸭

动态开点线段树 使用场景 \(4 \times n\) 开不下。 值域需要平移（有负数）。 什么时候开点 显然，访问的节点不存在时（只会在修改递归时开点）。 trick 区间里面有负数时，\(mid = (l + R – 1) / 2\)。 防止越界。 例如区间 \([-1,0]\)。 开点上限 考虑到 update 一次最多开 \(\log V\) 个点（…

前言 斜率优化是一种经典的单调队列优化类型，虽然它的名字很高大上，但是其思想内核非常简单，这篇博客就是用来帮助各位快速入门的 提示：本博客以单调队列的思想理解斜率优化 引入 dp 优化可以怎么分类？ 数据结构维护决策点集的插入与查找 算法维护决策点集大小，取出无用决策点 而斜率优化 dp 属于第二者，且常常用于优化序列分割问题 Q1 P3195 A1 先列出…