OI-wiki 斜率优化 DP 完全指南从玩具装箱到凸包、CDQ 分治与平衡树【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki斜率优化Convex Hull TrickCHT是动态规划中一类极具代表性的优化技术它将形如 $f_i\min_{ji}{f_jw(i,j)}$ 的转移方程通过代数变换转化为二维平面上用直线切凸包求最小截距的几何问题从而把 $O(n^2)$ 的朴素 DP 降到 $O(n)$。本文以 OI-wiki 仓库 docs/dp/opt/slope.md 为骨架以「HNOI2008 玩具装箱」为主线完整推导斜率优化的建模过程与凸包维护细节并深入讲解当斜率单调性、横坐标单调性缺失时如何用二分、平衡树与 CDQ 分治CDQ 分治进行推广。读完本文你将掌握如何把任意 $O(n^2)$ 的 1D/1D 转移方程改写为截距最值形式如何用单调队列维护下凸壳并均摊 $O(1)$ 求解以及斜率不单调时 $O(n\log^2 n)$ 的 CDQ 分治做法。例题引入HNOI2008 玩具装箱有 $n$ 个玩具排成一排第 $i$ 个玩具价值为 $c_i$要求将这 $n$ 个玩具分成若干段。对于一段 $[l,r]$它的代价为$$ (r-l\sum_{il}^r c_i-L)^2 $$其中 $L$ 是常量求分段的最小代价。数据范围为 $1\le n\le 5\times 10^4,\ 1\le L,c_i\le 10^7$。这个数据规模直接否决了 $O(n^2)$ 的朴素做法而平方项的存在又提示我们展开后会出现 $i\cdot j$ 的交叉项这正是斜率优化CHT的典型信号。朴素 DP 做法令 $f_i$ 表示前 $i$ 个物品分若干段的最小代价枚举最后一段的起点 $j1$则有状态转移方程$$ f_i\min_{ji}{f_j(i-(j1)pre_i-pre_j-L)^2}\min_{ji}{f_j(pre_i-pre_ji-j-1-L)^2} $$其中 $pre_i\sum_{k1}^{i}c_k$ 是前缀和。由于每次转移需要枚举全部 $ji$朴素实现的时间复杂度为 $O(n^2)$在 $n5\times10^4$ 时无法承受。简化转移方程观察括号内的项 $pre_i-pre_ji-j-1-L$可以令$$ s_ipre_ii,\qquad LL1 $$于是转移方程简化为$$ f_i\min_{ji}{f_j(s_i-s_j-L)^2} $$几何建模把 DP 化成截距最值问题将平方展开并把与 $j$ 无关的项移到 $\min$ 外$$ f_i-(s_i-L)^2\min_{ji}{f_js_j^22s_j(L-s_i)} $$回忆一次函数的斜截式 $ykxb$移项得到 $by-kx$。我们做如下对应把与 $j$决策点有关的信息放进 $y$把同时与 $i,j$ 有关的信息放进 $kx$把与 $i$ 有关、需要最小化的信息放进 $b$截距。具体地设$$ \begin{aligned} x_js_j\ y_jf_js_j^2\ k_i-2(L-s_i)\ b_if_i-(s_i-L)^2 \end{aligned} $$则转移方程写作$$ b_i\min_{ji}{y_j-k_ix_j} $$此时 $(x_j,y_j)$ 是二维平面上的点$k_i$ 是直线斜率$b_i$ 是过点 $(x_j,y_j)$、斜率为 $k_i$ 的直线在 $y$ 轴上的截距。原问题就此转化为在已有决策点集中选择点 $j$使过该点、斜率为 $k_i$ 的直线截距最小。如上图docs/dp/images/optimization.svg将斜率为 $k_i$ 的直线从下往上平移直到某个点 $(x_p,y_p)$ 落在直线上此时 $b_iy_p-k_ix_p$ 取到最小值。算完 $f_i$ 后把新点 $(x_i,y_i)$ 加入点集作为后续转移的候选决策。为什么只需维护下凸壳容易发现能使 $b_i$ 取到最小值的点一定落在下凸壳上位于凸包内部的点无论直线斜率如何都不可能最先被切到。因此寻找 $p$ 时无需枚举全部 $i-1$ 个点只需考察凸包顶点。更进一步在本题中 $k_i$ 随 $i$ 递增而单调递增于是可以用单调队列维护凸包配合队首指针实现均摊 $O(1)$ 的查询。单调队列维护下凸壳记 $K(a,b)$ 为过点 $(x_a,y_a)$ 与 $(x_b,y_b)$ 的直线斜率。队列 $q_l,q_{l1},\ldots,q_r$ 维护的是下凸壳上的点即对任意 $lir$始终有$$ K(q_{i-1},q_i)K(q_i,q_{i1}) $$也就是说凸壳上相邻点的斜率严格递增这正是后续二分的基础。查询用直线切凸壳维护一个指针 $e$寻找满足$$ K(q_{e-1},q_e)\le k_i K(q_e,q_{e1}) $$的 $e$当 $el$ 或 $er$ 时做边界特判此时 $pq_e$ 即为最优决策点。由于 $k_i$ 单调递增$e$ 只会向右移动总移动次数均摊 $O(1)$。插入维护凸性插入新点 $(x_i,y_i)$ 时先判断$$ K(q_{r-1},q_r)K(q_r,i) $$若不等式不成立说明 $q_r$ 已不可能再成为凸壳顶点将其从队尾弹出重复直到不等式成立再把 $i$ 入队。这保证了新点加入后队列依然满足相邻斜率严格递增的凸性条件。至此DP 的复杂度从 $O(n^2)$ 优化到了 $O(n)$。算法流程概括将初始状态边界点入队。对每个 $i$使用与 $i$ 相关的直线 $f(i)$ 去切维护的凸包找到最优决策点更新 $dp_i$。加入状态 $dp_i$若某状态在 $dp_i$ 加入后不再是凸包上的点需在入队前将其剔除。斜率优化的适用范围不限于玩具装箱同一框架变换 → 建点 → 维护凸壳 → 直线切凸壳可推广到大量带平方代价或交叉项的 1D/1D DP例如后文习题中的仓库建设、特别行动队、货币兑换等经典问题。进阶当单调性缺失——二分、平衡树与 CDQ 分治上面之所以能用单调队列依赖两个关键性质查询时直线的斜率 $k_i$ 随 $i$ 单调变化插入时决策点的横坐标 $x_js_j$ 单调递增。玩具装箱改价值可以为负考虑「玩具装箱」的变体唯一区别是玩具价值可以为负即 $1\le n\le 5\times10^4,\ 1\le L\le 10^7,\ -10^7\le c_i\le 10^7$。沿用之前的定义令 $f_i$ 表示前 $i$ 个物品分段的最小代价转移方程为$$ f_i\min_{ji}{f_j(pre_i-pre_ji-j-1-L)^2} $$做相同的变换后得到$$ f_i-(s_i-L)^2\min_{ji}{f_js_j^22s_j(L-s_i)} $$然而此时两个条件都不再成立直线的斜率不再单调$c_i$ 可为负导致 $s_i$ 不单调进而 $k_i-2(L-s_i)$ 不单调队首指针 $e$ 无法只向右移动决策点的横坐标不再单调$x_js_j$ 不单调新点可能插入到凸壳中间无法简单地从队尾入队。但凸壳本身仍然存在问题变为如何在不单调的两种意义下维护和查询凸壳。查询端凸壳上二分在寻找最优决策、即用直线切凸壳时把单调队列找队首改为在凸壳上二分由于凸壳上相邻两点的斜率 $K(q_{i-1},q_i)$ 具有单调性可以二分出斜率最接近 $k_i$ 的那条凸壳边其端点即为最优决策。二分将单次查询从均摊 $O(1)$ 变为 $O(\log n)$。插入端两种维护方案方案一平衡树维护凸壳。用平衡树直接维护凸壳上的点查询决策点时在平衡树上二分插入决策点时在平衡树上插入结点并删除若干被踢出凸壳的点。此方法思路简洁但实现繁琐需要维护前驱后继斜率关系。方案二CDQ 分治推荐。OI-wiki 在 docs/misc/cdq-divide.md 中系统介绍了 CDQ 分治并将其列为三类主要应用之一1D 动态规划的优化与转移。下面展开基于 CDQ 分治的斜率优化做法。CDQ 分治优化斜率 DP设 $\text{CDQ}(l,r)$ 负责计算 $f_i,\ i\in[l,r]$。考虑 $\text{CDQ}(1,n)$ 的流程先调用 $\text{CDQ}(1,mid)$ 算出 $f_i,\ i\in[1,mid]$对 $[1,mid]$ 内的决策点此时全部已算毕静态建凸壳用这个凸壳去更新 $f_i,\ i\in[mid1,n]$由于此时决策点集固定不变不像原问题边算 DP 边加决策点可以把 $i\in[mid1,n]$ 的 $f_i$ 按直线斜率 $k_i$ 排序再用单调队列计算 DP 值当然也可以在静态凸壳上二分计算对 $[mid1,n]$ 中的每个点若其最优决策恰在 $[1,mid]$则在这一步就被更新成最优答案。执行完这一步后$[1,mid]$ 中的点已发挥全部作用可以整体舍弃该区间递归调用 $\text{CDQ}(mid1,n)$ 解决右区间剩下的问题。每次合并的复杂度为 $O(n\log n)$排序或建凸壳总时间复杂度为 $O(n\log^2 n)$。为什么 CDQ 能正确处理CDQ 分治优化 DP 与处理点对问题的 CDQ 写法有一个关键差异转移必须夹在两次递归之间先solve(l,mid)再处理跨区间转移最后solve(mid1,r)因为 DP 转移是有序的必须满足两个条件用来计算 $f_i$ 的所有 $f_j$ 都必须已计算完毕不能存在半成品用来计算 $f_i$ 的所有 $f_j$ 都必须能更新到 $f_i$不能有漏更。在 CDQ 的递归结构下一个 $i$ 点的 DP 值会被更新 $O(\log n)$ 次而更新它的区间恰好是 $(1,i)$ 在线段树/分治树上被拆分出的 $O(\log n)$ 个不相交区间。因此所有合法的 $ji$ 都恰好覆盖了 $i$正确性得以保证。关于该递归树结构与正确性证明的完整讨论可参见 docs/misc/cdq-divide.md 中的「CDQ 分治优化 1D/1D 动态规划的转移」一节。两种思路的对比小结对比「玩具装箱」与「玩具装箱 改」可以总结出两点方法论二分、CDQ、平衡树等工具能够优化 DP 方程的计算在一定程度降低复杂度但不能改变方程本身DP 方程的性质斜率是否单调、横坐标是否单调取决于数据的特征而 DP 方程本身取决于题目中的数学模型。做题时应先建立模型再根据数据特征选择合适的凸壳维护与查询手段。小结斜率优化 DP 的核心宗旨是把最优化问题转化为二维平面上与凸包有关的截距最值问题。实战中的完整套路是写出 $O(n^2)$ 转移方程通过代数变换分离出 $(i,j)$ 交叉项设 $x_j,y_j,k_i,b_i$ 将转移改写为 $b_i\min{y_j-k_ix_j}$ 的切凸壳形式性质好斜率单调、横坐标单调时用单调队列$O(n)$ 解决性质不好时查询端用凸壳上二分插入端用平衡树或 CDQ 分治$O(n\log n)$ 到 $O(n\log^2 n)$ 解决遇到性质更差的方程有时还需辅以李超线段树见 docs/ds/li-chao-tree.md仓库中的 李超树实现等数据结构届时请就题而论。习题以下经典题目覆盖了斜率优化从入门到进阶的各个层次建议按顺序练习「SDOI2016」征途方差/平方代价的经典应用「ZJOI2007」仓库建设带线性项与固定费用的斜率优化「APIO2010」特别行动队上凸壳 单调队列「JSOI2011」柠檬横坐标不单调的变体「CF 311B」Cats Transport多阶段斜率优化「NOI2007」货币兑换横纵坐标均不单调需平衡树/CDQ 维护凸壳「NOI2019」回家路线斜率优化与最短路结合的进阶题「NOI2016」国王饮水记斜率优化 精度控制的综合题「NOI2014」购票树上斜率优化 数据结构维护【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 斜率优化 DP 完全指南：从玩具装箱到凸包、CDQ 分治与平衡树
OI-wiki 斜率优化 DP 完全指南从玩具装箱到凸包、CDQ 分治与平衡树【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki斜率优化Convex Hull TrickCHT是动态规划中一类极具代表性的优化技术它将形如 $f_i\min_{ji}{f_jw(i,j)}$ 的转移方程通过代数变换转化为二维平面上用直线切凸包求最小截距的几何问题从而把 $O(n^2)$ 的朴素 DP 降到 $O(n)$。本文以 OI-wiki 仓库 docs/dp/opt/slope.md 为骨架以「HNOI2008 玩具装箱」为主线完整推导斜率优化的建模过程与凸包维护细节并深入讲解当斜率单调性、横坐标单调性缺失时如何用二分、平衡树与 CDQ 分治CDQ 分治进行推广。读完本文你将掌握如何把任意 $O(n^2)$ 的 1D/1D 转移方程改写为截距最值形式如何用单调队列维护下凸壳并均摊 $O(1)$ 求解以及斜率不单调时 $O(n\log^2 n)$ 的 CDQ 分治做法。例题引入HNOI2008 玩具装箱有 $n$ 个玩具排成一排第 $i$ 个玩具价值为 $c_i$要求将这 $n$ 个玩具分成若干段。对于一段 $[l,r]$它的代价为$$ (r-l\sum_{il}^r c_i-L)^2 $$其中 $L$ 是常量求分段的最小代价。数据范围为 $1\le n\le 5\times 10^4,\ 1\le L,c_i\le 10^7$。这个数据规模直接否决了 $O(n^2)$ 的朴素做法而平方项的存在又提示我们展开后会出现 $i\cdot j$ 的交叉项这正是斜率优化CHT的典型信号。朴素 DP 做法令 $f_i$ 表示前 $i$ 个物品分若干段的最小代价枚举最后一段的起点 $j1$则有状态转移方程$$ f_i\min_{ji}{f_j(i-(j1)pre_i-pre_j-L)^2}\min_{ji}{f_j(pre_i-pre_ji-j-1-L)^2} $$其中 $pre_i\sum_{k1}^{i}c_k$ 是前缀和。由于每次转移需要枚举全部 $ji$朴素实现的时间复杂度为 $O(n^2)$在 $n5\times10^4$ 时无法承受。简化转移方程观察括号内的项 $pre_i-pre_ji-j-1-L$可以令$$ s_ipre_ii,\qquad LL1 $$于是转移方程简化为$$ f_i\min_{ji}{f_j(s_i-s_j-L)^2} $$几何建模把 DP 化成截距最值问题将平方展开并把与 $j$ 无关的项移到 $\min$ 外$$ f_i-(s_i-L)^2\min_{ji}{f_js_j^22s_j(L-s_i)} $$回忆一次函数的斜截式 $ykxb$移项得到 $by-kx$。我们做如下对应把与 $j$决策点有关的信息放进 $y$把同时与 $i,j$ 有关的信息放进 $kx$把与 $i$ 有关、需要最小化的信息放进 $b$截距。具体地设$$ \begin{aligned} x_js_j\ y_jf_js_j^2\ k_i-2(L-s_i)\ b_if_i-(s_i-L)^2 \end{aligned} $$则转移方程写作$$ b_i\min_{ji}{y_j-k_ix_j} $$此时 $(x_j,y_j)$ 是二维平面上的点$k_i$ 是直线斜率$b_i$ 是过点 $(x_j,y_j)$、斜率为 $k_i$ 的直线在 $y$ 轴上的截距。原问题就此转化为在已有决策点集中选择点 $j$使过该点、斜率为 $k_i$ 的直线截距最小。如上图docs/dp/images/optimization.svg将斜率为 $k_i$ 的直线从下往上平移直到某个点 $(x_p,y_p)$ 落在直线上此时 $b_iy_p-k_ix_p$ 取到最小值。算完 $f_i$ 后把新点 $(x_i,y_i)$ 加入点集作为后续转移的候选决策。为什么只需维护下凸壳容易发现能使 $b_i$ 取到最小值的点一定落在下凸壳上位于凸包内部的点无论直线斜率如何都不可能最先被切到。因此寻找 $p$ 时无需枚举全部 $i-1$ 个点只需考察凸包顶点。更进一步在本题中 $k_i$ 随 $i$ 递增而单调递增于是可以用单调队列维护凸包配合队首指针实现均摊 $O(1)$ 的查询。单调队列维护下凸壳记 $K(a,b)$ 为过点 $(x_a,y_a)$ 与 $(x_b,y_b)$ 的直线斜率。队列 $q_l,q_{l1},\ldots,q_r$ 维护的是下凸壳上的点即对任意 $lir$始终有$$ K(q_{i-1},q_i)K(q_i,q_{i1}) $$也就是说凸壳上相邻点的斜率严格递增这正是后续二分的基础。查询用直线切凸壳维护一个指针 $e$寻找满足$$ K(q_{e-1},q_e)\le k_i K(q_e,q_{e1}) $$的 $e$当 $el$ 或 $er$ 时做边界特判此时 $pq_e$ 即为最优决策点。由于 $k_i$ 单调递增$e$ 只会向右移动总移动次数均摊 $O(1)$。插入维护凸性插入新点 $(x_i,y_i)$ 时先判断$$ K(q_{r-1},q_r)K(q_r,i) $$若不等式不成立说明 $q_r$ 已不可能再成为凸壳顶点将其从队尾弹出重复直到不等式成立再把 $i$ 入队。这保证了新点加入后队列依然满足相邻斜率严格递增的凸性条件。至此DP 的复杂度从 $O(n^2)$ 优化到了 $O(n)$。算法流程概括将初始状态边界点入队。对每个 $i$使用与 $i$ 相关的直线 $f(i)$ 去切维护的凸包找到最优决策点更新 $dp_i$。加入状态 $dp_i$若某状态在 $dp_i$ 加入后不再是凸包上的点需在入队前将其剔除。斜率优化的适用范围不限于玩具装箱同一框架变换 → 建点 → 维护凸壳 → 直线切凸壳可推广到大量带平方代价或交叉项的 1D/1D DP例如后文习题中的仓库建设、特别行动队、货币兑换等经典问题。进阶当单调性缺失——二分、平衡树与 CDQ 分治上面之所以能用单调队列依赖两个关键性质查询时直线的斜率 $k_i$ 随 $i$ 单调变化插入时决策点的横坐标 $x_js_j$ 单调递增。玩具装箱改价值可以为负考虑「玩具装箱」的变体唯一区别是玩具价值可以为负即 $1\le n\le 5\times10^4,\ 1\le L\le 10^7,\ -10^7\le c_i\le 10^7$。沿用之前的定义令 $f_i$ 表示前 $i$ 个物品分段的最小代价转移方程为$$ f_i\min_{ji}{f_j(pre_i-pre_ji-j-1-L)^2} $$做相同的变换后得到$$ f_i-(s_i-L)^2\min_{ji}{f_js_j^22s_j(L-s_i)} $$然而此时两个条件都不再成立直线的斜率不再单调$c_i$ 可为负导致 $s_i$ 不单调进而 $k_i-2(L-s_i)$ 不单调队首指针 $e$ 无法只向右移动决策点的横坐标不再单调$x_js_j$ 不单调新点可能插入到凸壳中间无法简单地从队尾入队。但凸壳本身仍然存在问题变为如何在不单调的两种意义下维护和查询凸壳。查询端凸壳上二分在寻找最优决策、即用直线切凸壳时把单调队列找队首改为在凸壳上二分由于凸壳上相邻两点的斜率 $K(q_{i-1},q_i)$ 具有单调性可以二分出斜率最接近 $k_i$ 的那条凸壳边其端点即为最优决策。二分将单次查询从均摊 $O(1)$ 变为 $O(\log n)$。插入端两种维护方案方案一平衡树维护凸壳。用平衡树直接维护凸壳上的点查询决策点时在平衡树上二分插入决策点时在平衡树上插入结点并删除若干被踢出凸壳的点。此方法思路简洁但实现繁琐需要维护前驱后继斜率关系。方案二CDQ 分治推荐。OI-wiki 在 docs/misc/cdq-divide.md 中系统介绍了 CDQ 分治并将其列为三类主要应用之一1D 动态规划的优化与转移。下面展开基于 CDQ 分治的斜率优化做法。CDQ 分治优化斜率 DP设 $\text{CDQ}(l,r)$ 负责计算 $f_i,\ i\in[l,r]$。考虑 $\text{CDQ}(1,n)$ 的流程先调用 $\text{CDQ}(1,mid)$ 算出 $f_i,\ i\in[1,mid]$对 $[1,mid]$ 内的决策点此时全部已算毕静态建凸壳用这个凸壳去更新 $f_i,\ i\in[mid1,n]$由于此时决策点集固定不变不像原问题边算 DP 边加决策点可以把 $i\in[mid1,n]$ 的 $f_i$ 按直线斜率 $k_i$ 排序再用单调队列计算 DP 值当然也可以在静态凸壳上二分计算对 $[mid1,n]$ 中的每个点若其最优决策恰在 $[1,mid]$则在这一步就被更新成最优答案。执行完这一步后$[1,mid]$ 中的点已发挥全部作用可以整体舍弃该区间递归调用 $\text{CDQ}(mid1,n)$ 解决右区间剩下的问题。每次合并的复杂度为 $O(n\log n)$排序或建凸壳总时间复杂度为 $O(n\log^2 n)$。为什么 CDQ 能正确处理CDQ 分治优化 DP 与处理点对问题的 CDQ 写法有一个关键差异转移必须夹在两次递归之间先solve(l,mid)再处理跨区间转移最后solve(mid1,r)因为 DP 转移是有序的必须满足两个条件用来计算 $f_i$ 的所有 $f_j$ 都必须已计算完毕不能存在半成品用来计算 $f_i$ 的所有 $f_j$ 都必须能更新到 $f_i$不能有漏更。在 CDQ 的递归结构下一个 $i$ 点的 DP 值会被更新 $O(\log n)$ 次而更新它的区间恰好是 $(1,i)$ 在线段树/分治树上被拆分出的 $O(\log n)$ 个不相交区间。因此所有合法的 $ji$ 都恰好覆盖了 $i$正确性得以保证。关于该递归树结构与正确性证明的完整讨论可参见 docs/misc/cdq-divide.md 中的「CDQ 分治优化 1D/1D 动态规划的转移」一节。两种思路的对比小结对比「玩具装箱」与「玩具装箱 改」可以总结出两点方法论二分、CDQ、平衡树等工具能够优化 DP 方程的计算在一定程度降低复杂度但不能改变方程本身DP 方程的性质斜率是否单调、横坐标是否单调取决于数据的特征而 DP 方程本身取决于题目中的数学模型。做题时应先建立模型再根据数据特征选择合适的凸壳维护与查询手段。小结斜率优化 DP 的核心宗旨是把最优化问题转化为二维平面上与凸包有关的截距最值问题。实战中的完整套路是写出 $O(n^2)$ 转移方程通过代数变换分离出 $(i,j)$ 交叉项设 $x_j,y_j,k_i,b_i$ 将转移改写为 $b_i\min{y_j-k_ix_j}$ 的切凸壳形式性质好斜率单调、横坐标单调时用单调队列$O(n)$ 解决性质不好时查询端用凸壳上二分插入端用平衡树或 CDQ 分治$O(n\log n)$ 到 $O(n\log^2 n)$ 解决遇到性质更差的方程有时还需辅以李超线段树见 docs/ds/li-chao-tree.md仓库中的 李超树实现等数据结构届时请就题而论。习题以下经典题目覆盖了斜率优化从入门到进阶的各个层次建议按顺序练习「SDOI2016」征途方差/平方代价的经典应用「ZJOI2007」仓库建设带线性项与固定费用的斜率优化「APIO2010」特别行动队上凸壳 单调队列「JSOI2011」柠檬横坐标不单调的变体「CF 311B」Cats Transport多阶段斜率优化「NOI2007」货币兑换横纵坐标均不单调需平衡树/CDQ 维护凸壳「NOI2019」回家路线斜率优化与最短路结合的进阶题「NOI2016」国王饮水记斜率优化 精度控制的综合题「NOI2014」购票树上斜率优化 数据结构维护【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考