slope trick 学习笔记

对于一个凸函数 $f_x$，若其满足如下性质，则可以使用 slope trick 来刻画：

• $f_x$ 是连续的，即定义域为一个区间；
• $f_x$ 由若干段首尾相连的一次函数拼接而成，且这些一次函数的斜率均为整数；
• 设这些一次函数的斜率的极差为 $v$，则 $v$ 很小（$O(v)$ 可接受）；

具体的，不妨设 $f_x$ 为下凸函数，且其定义域从 $0$ 开始。

注意到每一段一次函数首尾相连，斜率极差很小，且斜率单调不降。所以可以用 $f_0$、第一段一次函数的斜率 $k_0$ 和斜率增加点的可重集合 $S$ 来刻画 $f$。具体的，若斜率在某个位置 $x$ 增加了 $\Delta k$，则在 $S$ 中插入 $\Delta k$ 个 $x$。

例如 $f_{[0,4]}=[1,-1,-3,1,6]$ 这个下凸函数就可以用 $f_0=1,k_0=-2,S=\{2,2,2,2,2,2,3\}$ 来描述。

这样刻画的函数性质十分好：

• 加法：直接将 $f_0$ 和 $k_0$ 分别相加，并合并两个可重集 $S$；
• 求前缀/后缀 min：去掉后面斜率 $>0$ 或者前面斜率 $<0$ 的部分，对应于删除 $S$ 中最大或最小的若干个数；
• 求全局 min：提取斜率为 $0$ 的部分；

并且很容易刻画和绝对值相关的操作。

实际一般使用堆/平衡树来维护 $S$。

例题：P3642 [APIO2016] 烟火表演