我会凸性
AC_Lover
·
·
算法·理论
Slope Trick
理论
**重要性质：（凸函数的封闭性）**
若 $f,g$ 为凸函数：
1. $f+g$ 也是凸函数
2. 令 $\lambda\ge 0$，则 $\lambda f$ 也为凸函数
3. $\max(f,g)$ 是凸函数
4. $h(x)=\min\limits_k \set{f(k)+g(x-k)}$ 也是凸的（闵可夫斯基和）
**常用技巧：**
- 用堆等数据结构维护拐点，若一个拐点 $x_i$ 在堆中出现了 $k$ 次则表示斜率在此处 $\pm k$。
- 平衡树、堆维护函数斜率
## 例题
### 例一：[P4331 [BalticOI 2004] Sequence (Day1)](https://www.luogu.com.cn/problem/P4331)
先将所有 $t_i$ 变成 $t_i-i$，这样我们要求的 $z_i$ 就要求是非严格单调递减的。于是我们可以设计一个简单的 $\mathrm{dp}$，令 $f_i(x)$ 表示考虑前 $i$ 项，$z_i=x$ 时的绝对值最小值，于是我们可以得到转移：
$$
f_i(x)=\min_yf_{i-1}(y)+|t_i-x|
$$
令 $g_{i-1}(x)=\min\limits_y f_{i-1}(y)$，则可以写成 $f_i(x)=g_{i-1}(x)+|t_i-x|$，分析一下，我们发现 $g$ 是前缀 $\min$，显然是凸的，并且绝对值 $|t_i-x|$ 是一个关于 $t_i$ 对称的两条斜率分别为 $-1,+1$ 的直线，也是凸的，因此两个凸函数的和 $f$ 也是凸的。因此可以使用凸性优化。
考虑画出函数的情况：
考虑用堆维护凸函数 $f$，维护这个凸函数的拐点（即每两段一次函数的衔接点），其中拐点 $x$ 在堆中出现 $k$ 次体现这个函数在 $x$ 处变化的斜率为 $-k$。
那么在加上 $|t_i-x|$ 时，$x=t_i$ 左侧所有斜率 $-1$，右侧所有斜率 $+1$，这等价于 $x=t_i$ 处的斜率变化量为 $-2$，因此直接在堆中扔两个 $t_i$，而右边的平台在 $+1$ 后会抬起来。再对这个函数求前缀 $\min$ 转化到 $g$，那么前面的部分没有变化，后面抬起来的部分会被压下去，因此我们要将抬起来的压下去，相当于要将右边斜率变得 $>0$ 的部分删掉，分析一下，斜率 $-i,-i+1,\dots,0,1$，那么我们只需要保留存储着 $[-i,0]$ 部分的拐点，总计有 $i$ 个（最左边的不用存），于是我们一直在大根堆大小大于 $i$ 时从大根堆中弹掉拐点即可。
考虑怎么求出方案。假设我们已经确定了 $z_{i+1}$，考虑求 $f_i(x)$ 的最优决策点 $p_i$（即最低点平台），这个在维护大根堆跑到 $i$ 时取出最靠右的拐点，即取出堆顶即可，如果 $p_{i}\le z_{i+1}$ 那么可以直接令 $z_i=p_i$，这样没有矛盾，但是如果 $p_i>z_{i+1}$ 就会发生冲突，此时我们必须维持 $z_i\le z_{i+1}$，观察函数图像，我们尽可能往右取就是最优的，因此此时令 $z_i=z_{i+1}$。综上我们得到 $z_i=\min(p_i,z_{i+1})$。求出 $z_i$ 也自然可以随便求出答案。
时间复杂度 $O(n\log n)$。
### 例二：[P11598 [NOISG 2018 Finals] Safety](https://www.luogu.com.cn/problem/P11598)
令 $f_i(x)$ 表示考虑前 $i$ 根柱子，且第 $i$ 根柱子被调节成高度为 $x$ 的最小代价。不难得到：
$$
f_i(x)=\min_{x-H\le y\le x+H} f_{i-1}(y)+|h_i-x|
$$
令前面的一坨 $g_{i-1}(x)=\min\limits_{x-H\le y\le x+H} f_{i-1}(y)$，则 $f_i(x)=g_{i-1}(x)+|h_i-x|$。我们注意到 $f_0(x)=0$，因此初值是凸的，并且 $g_{i-1}(x)$ 是拿一段取 $\min$，也是凸的，并且 $|h_i-x|$ 也是凸的，综上有 $f_i(x)$ 是凸的。
考虑 $g_{i-1}(x)$ 在干嘛：
其相当于将原来的图像按最低点劈开，然后左边部分往左移 $H$，右边部分往右移 $H$。
还是套路地考虑用堆来维护拐点，只不过这次要用两个堆，用大根堆维护左边的拐点，小根堆维护右边的拐点。由于要支持左右平移，所以我们要支持全局加，这个看似很困难，甚至以为要用平衡树，但其实没有必要，假设有一个堆 $Q$，我们要支持全局加，那么可以对其维护一个全局加的偏移量 $\Delta$，如果要插入一个数 $x$，那么我们转而向堆中加入 $x-\Delta$，而查询时返回 $x+\Delta^\prime$ 即可。
现在还有一个加绝对值，与上一题类似，是在 $h_i$ 的左侧将斜率 $-1$，在右侧将斜率 $+1$，只不过这次要分类讨论，令中间平台是区间 $[L,R]$：
- 若 $h_i$ 在平台上，即 $h_i\in [L,R]$，此时相当于将两边的平台抬起来，直接在左右的堆中都加入拐点 $h_i$ 即可，最优决策点没有变化，并且最优点就取在 $x=h_i$ 处，对最低点没有贡献。
- 若 $h_i$ 加在左半部分，即 $x\le L$。那么加完之后中间的平台会抬起来，左边平下去一段，那这样相当于将原来平台的拐点 $L$ 从左边部分扔到了右边部分。此时会发生变化：
此时平台往左上移动了，考虑平台的函数值的变化，我们发现新函数的平台和原函数的平台在左右端点处相交了，因此我们可以直接取原平台的左端点 $x=L$ 处的函数值作为平台的值，增量就是 $|h_i-L|=L-h_i$，直接将这个贡献到答案中即可。
- 若 $h_i$ 加在右半部分，即 $x\ge R$，与左边同理。
直接维护即可，时间复杂度 $O(n\log n)$。
:::info[代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int n,H; int h[N];
priority_queue<ll> ql;
priority_queue<ll,vector<ll>,greater<ll> > qr;
ll lt,rt;
ll topl() { return ql.top()+lt; }
ll topr() { return qr.top()+rt; }
void pushl(ll x) { ql.push(x-lt); }
void pushr(ll x) { qr.push(x-rt); }
int main()
{
cin >> n >> H;
for (int i=1;i<=n;i++) cin >> h[i];
pushl(-1e18), pushr(1e18); ll ans=0;
for (int i=1;i<=n;i++)
{
lt-=H, rt+=H;
if (topl()>=h[i]) //left
{
ll x=topl(); pushr(x); ql.pop();
pushl(h[i]), pushl(h[i]);
ans+=x-h[i];
}
else if (h[i]>=topr())
{
ll x=topr(); pushl(x); qr.pop();
pushr(h[i]), pushr(h[i]);
ans+=h[i]-x;
}
else pushl(h[i]), pushr(h[i]);
while (ql.size() && topl()<0) ql.pop();
}
cout << ans << "\n";
return 0;
}
```
:::
### 例三：[P3642 APIO2016 烟火表演](https://www.luogu.com.cn/problem/P3642)
定义 $f_u(x)$ 表示 $u$ 为根的子树内所有烟花都在 $i$ 时刻燃爆的最少代价，易得转移：
$$
f_u(x)=\sum_{v} \left(\min_{0\le i\le x}\set{f_v(i)+|w-(x-i)|}\right)
$$
很明显这是一堆绝对值函数的和，一定是一个下凸包
将后面的一部分表示出来
$$
f^\prime(x)=\min_{0\le i\le x}\set{f_v(i)+|w-(x-i)|}
$$
考虑 $f^\prime$ 和 $f_v$ 的关系
$f_v$ 是下凸包，中间有一段斜率为 $0$ 的最小值区间 $[L,R]$，记其最小值为 $f(\min)$：
接下来分讨：
- $x\le L
此时让 i 取到 x 一定最优，f^\prime(x)=f(x)+w
-
L<x\le L+w
此时让 i 取到 L 一定最优，f^\prime(x)=f(L)+|w-(x-L)|=f(\min)+w-x+L
-
L+w<x\le R+w
此时让 i 取到 x-w 一定最优，f^\prime(x)=f(x-w)=f(\min)
-
R+w<x
此时让 i 取到 R 一定最优，f^\prime(x)=f(R)+|w-(x-R)|=f(\min)+x-R-w
可以发现操作对应了【向上平移 w 】、【变成一个斜率为 -1 的直线】、【 [L,R] 向右平移到 [L+w,R+w] 】、【变成一个斜率为 1 的直线】
因此拐点的变化只有删去 L,R 增加 L+w,R+w，于是用一个堆维护拐点，然后合并时使用左偏树 / 启发式合并合并拐点的堆。
然后我们得到了 1 号点的所有拐点的堆，考虑如何计算答案
由于 x\le L 的部分每次都会加上 w，所以 f_{1,0} 其实是所有边的边权和，于是我们根据存储拐点的堆的定义，每次弹出时减去就可以推出位于底层的答案。
例四：P11678 [USACO25JAN] Watering the Plants P
令 c_i 表示第 i 株植物需要的水量，w_i 表示连接 i,i+1 的水渠的单位代价。
定义 f_i(j) 表示前 i 株植物已经搞定并且给第 i+1 株植物额外贡献了 j 的水量时的最小代价，转移是简单的，枚举第 i-1 个水渠用了 k 的水，于是
f_i(j)=\min_{k+j\ge c_i}\set{f_{i-1}(k)+j\times w_i} \\
=\min_{k\ge \max(0,c_i-j)}f_{i-1}(k)+j\times w_i
使用后缀 \min 优化一下：
g_i(j)=\min_{k\ge j}f_i(k) \\
f_i(j)=g_{i-1}(\max(0,c_i-j))+j\times w_i
我们将 j 分类：
-
j\le c_i$，有：$f_i(j)=g_{i-1}(c_i-j)+j\times w_i
-
j>c_i$，有：$f_i(j)=g_{i-1}(0)+j\times w_i
由于 g_{i-1}(0) 在 g_{i-1} 中为最大值，可以发现 f_i 是凸的，由此考虑凸性优化。
还是分开来看：
做完之后，全部推成后缀 \min，后缀 \min 一定是一个平台加上一个单调上升。即：
我们考虑维护点到点斜率，注意，此处的斜率其实相当于 f 的差分。
观察转移式，我们要求的答案是 f_i(0)，可以发现 f_i(0)=g_{i-1}(c_i)，如何求 g_{i-1}(c_i)？注意到我们是知道 f_{i-1}(0) 的，那么可以通过斜率推导一下：
具体的，我们令 s 表示斜率 k<0 的部分的斜率之和，那么通过 f_{i-1}(0)+s 即可算出 g_{i-1}(0)，即图中蓝色平台的高度。我们知道 g_{i-1,0}，那么从前往后加上斜率加到 c_i 就可以推出 g_{i-1,c_i}，这个的理解其实就是差分的前缀和是原数组，即令后面斜率 k>0 的部分到 c_i 的斜率和为 S，那么 g_{i-1}(c_i)=f_{i-1}(0)+s+S，也就是 f_i(0)。于是我们可以通过这种方式不断往后迭代，即可求解出所有的 f_i(0)。
维护斜率可以用平衡树，操作有【区间翻转】、【区间取反（翻转后斜率都取反）】、【覆盖成 0】、【加上 w_i】的操作，可以变成【区间翻转】、【区间乘】、【区间加】，用平衡树维护，并且要在平衡树上二分找到拐点推平，然后要计算前缀和，所以再维护一个前缀和。
然后就可以了，时间复杂度 O(n\log V)。
闵可夫斯基和
理论
两个凸包的闵和可以看做是把一个凸包的顶点不断换成另一个凸包顶点后最外层组成的凸多边形，这里不详细展开，主要分析下凸壳时的情况。
闵和主要是用来优化 \left(\min,+\right) 卷积的一个方法，有重要性质：
两个下凸壳的 \left(\min,+\right) 卷积依然是一个下凸壳
假设要把下凸壳 f,g 做 \left(\min,+\right) 卷积，即要计算
h_i=\min_{j+k=i}\set {f_j+g_k}
那么此时
h 的差分数组就是 f,g 差分数组的归并
有这个重要性质，就可以考虑用平衡树等数据结构快速维护凸壳的差分数组
例题
例一：P9962 [THUPC 2024 初赛] 一棵树
定义 f_{u,i} 表示考虑 u 为根的子树内，染了 i 个黑点时的最小代价，类比树形背包，得到转移：
f_{u,i}\leftarrow \min_{j+k=i}\set{f_{u,j}+f_{v,k}}
然后要加上代价，考虑 \mathrm{fa}_u\to u 这条边，上面有 K-i 个，下面有 i 个，于是差为 |K-i-i|=|K-2i|，于是
f_{u,i}\leftarrow f_{u,i}+|K-2i|
初值 f_{u,0}=f_{u,1}=0，最终目标：f_{1,k}
直接做背包时间和空间都不能接受，但是观察式子：
\min_{j+k=i}\set{f_{u,j}+f_{v,k}}
于是考虑使用闵和优化一下，很明显，此时 f_u 是 f_u 和 f_v 进行 (\min,+) 卷积得到的，如果我们维护 f_u,f_v 的差分数组，即维护第 i 个位置为 f^{\prime}_i 到 f^{\prime}_{i-1} 的差分，那么如果支持快速进行归并，即在值域上进行合并，那么就可以得出 f_u 的差分数组。而对于最后的 |K-2i|，这是绝对值函数，分类讨论一下
记 m=\lfloor\frac{K}{2}\rfloor
-
那么当 $i\le m$ 时贡献为 $K-2i$，是一个斜率为 $-2$ 的一次函数，对应在差分数组上相当于 $-2$。当 $i>m$ 时贡献为 $2i-K$，是一个斜率为 $2$ 的一次函数，同理相当于差分 $+2
-
那么当 $i\le m$ 时贡献为 $K-2i$，分析同上。当 $i=m+1$ 时，注意到 $|K-2(i-1)|=|K-2i|$，所以此时斜率变化为 $0$，不用管。而当 $i>m+1$ 时贡献为 $2i-K$，分析同上。
于是我们相当于要用一个数据结构维护差分数组，其支持值域上合并，区间加上一个数。很明显使用平衡树即可。其值域上合并的复杂度为 O(\log^2 n)，区间加可以打 \mathrm{tag}，于是就可以在 O(n\log^2 n) 的时间内求解出 f 的差分数组。
那么求答案也是简单的。考虑到我们已经求出了差分数组，只要知道 f_{1,0}，那么代入差分数组推下去就可以得到 f_{1,k}，f_{1,0} 在原来的 \mathrm{dp} 中很明显值为 (n-1)k，于是从前往后加上差分数组就做完了。
wqs二分
理论
wqs二分基于凸包。
常常用于强制选择 k 个满足某种属性的物品的最优化问题。
最优化问题转化成可行性问题，即判断是否选择 k 个。
设置一个偏移量 \Delta，对每个有限制的物品叠上 \Delta 进行影响，判断是否满足，然后二分，最后撤销 \Delta 得到答案。
例题
例一：P2619 [国家集训队] Tree I
简要题意： 给你一个无向带权连通图，每条边是黑色或白色。让你求 恰好有 K 条白色边 的 |\mathrm{MST}|。
分析：
最小生成树可以用Kruskal简单求解，但是此时强制要求选择 K 条白边，要分析性质。
定义 g_x 表示选择恰好 x 条白边时的 |\mathrm{MST}|，我们将 (x,g_x) 看做一个点放在平面直角坐标系里，可以发现这些点会构成一个下凸包，于是可以使用 wqs 二分。
我们要有一个办法来改变选择的白色边的数量，我们可以选择一个 \Delta，将所有白色边的权值都加上 \Delta，然后求这个新图的 |\mathrm{MST}|，假设选择了 k 条白边，如果 k\ge K，那么要选择少一点白边，让 \Delta 增加，否则让 \Delta 减少，由于刚刚分析的凸性，直接二分就可以找到 \Delta，然后减去加上的边权即可得到答案：ans=|\mathrm{MST}|-K\times \Delta。
例二：P4983 忘情
简要题意： 定义 a 的权值为 \left(\sum a_i+1\right)^2。
给定长度为 n 的序列 A，将其划分为恰好 m 段，权值定义为各段权值和，最小化权值。
分析：
先算出前缀和 s。
然后有一个显然的 \mathrm{DP}，定义 f_{i,j} 表示前 i 个数划分为恰好 j 段的最小权值，有
f_{i,j}=\min_{k<j} \set {f_{k,j-1}+(s_i-s_j+1)^2}
可以用斜优，但是最多优化到 O(nm)，考虑想办法分析性质优化掉 j。
由于 (a+b+1)^2\ge (a+1)^2+(b+1)^2，所以划分组数越多答案一定越小，因此设 g_x 表示划分为 x 组的答案，那么很明显 (x,g_x) 一定组成一个下凸包。
如果我们可以想办法影响最优解划分的组数，那么使用 \mathrm{wqs} 二分就可以解决了。
影响的方法也很简单，直接在每一次划分时加上一个划分代价 \Delta 即可，于是就可以先取消掉划分段数的限制进行 \mathrm{DP}。
f_i=\min_{j<i}\set{f_j+(s_i-s_j+1)^2+\Delta}
然后记录一个取到最优解时的划分段数 g，如果 g_n\le m 说明要划分更多，于是减少划分的代价，否则增加代价。
最后撤销代价，答案为 f_n-m\times \Delta。
其中 \mathrm{DP} 可以用斜率优化做到 O(n)，所以总时间复杂度 O(n\log V)。