凸优化常见技巧 做题笔记

· · 算法·理论

随着近期陆陆续续地被各种题目强碱灌输，最近在凸优化上好像终于入门了一点，至少不是像暑假之前那样完全不懂了。

感觉这类技巧还是十分深刻的，专门记录一下吧。

对于基础的知识点和算法流程这里可能写得不够详细，主要用于记录例题。

推荐阅读：

分为三部分：wqs 二分，闵可夫斯基和，slope trick。

wqs 二分

发现我真正理解 wqs 二分在干啥好像都是暑假之后的事了。

一般求解要求某个变量恰好为 k 的最值问题，设 f(k) 表示这个变量为 k 时的答案，我们首先要求 f(k) 是上凸/下凸的。

验证凸性的方式不少，最常见的就是感性理解、暴力打表、四边形不等式和费用流等。

因为 f(k) 是个凸壳，所以如果我们用一条斜率为 p 的直线去切凸壳，那么随着 p 的单调变化在凸壳上切到的点移动方向也是单调的。

那我们就二分斜率 p 去切题目里给的横坐标就好了，而 p 能切到的横坐标就是使得 f(x)-xp 最小的 x，找到这个 x 是比求 f(k) 要容易得多的。

不过有许多实现细节，要结合题目。假如我们最后二分出来的斜率是 p'，切点横坐标为 x，那么我们应该给答案加上 k\times p' 而不是 x\times p'，这是因为我们凸壳上可能会有斜率相同的共线情况，这时候我们会切到前面的点，但是反正这段斜率都一样所以直接加上是对的。

想起来之前@崔化博 突然问我斜率为什么可以只二分整数，凸壳上的点斜率是小数不就切不到了吗。

当时被问住了半天，但是其实 OI 里 f(k) 的定义域不一般是非负整数吗，凸壳上相邻两点横坐标之差是 1，所以斜率都是整数。

P2619 [国家集训队] Tree I

题目链接。

好像是经典的入门题，但是这题的凸性验证其实很困难啊。

令 f(k) 表示有恰好 k 条白边的最小生成树边权和，先认为我们知道 f(k) 是凸的。

二分斜率 mid，现在相当于要找到一个 x 使得 f(x)-x\times mid 取到最小值，给每条白边的边权减去 mid 跑 Kruskal 即可。

注意排序以颜色为第二关键字来处理凸壳上有共线。

感觉这题好像没啥好讲的啊。

代码。

ARC168E Subsegments with Large Sums

题目链接。

很有意思啊，需要多动点脑子，别掉坑里了。

直接想 wqs 二分就输了，因为你发现和 \ge s 的段数显然关于总段数不是凸的。

观察到题目本身就是具有单调性的，先二分答案 mid，现在问题就变成了判定是否可以划分成恰好 k 段使得 \ge s 的段数 \ge mid。

考虑这么刻画问题：对于一个划分的区间 [l,r] 定义它的代价为 r-l，设 f(x) 表示有 x 段的和 \ge s 需要的最小代价，相当于要判断是否满足 f(mid)\le n-k。发现 f(x) 关于 x 是下凸的，可以打表验证，或者理解成选的段代价会越来越大。

这样就对了，对着 f 再来一遍 wqs 二分，二分斜率 p 去切 f 这个下凸壳，这样一个 \ge s 的段代价会变成 r-l-p，我们只需要求出此时的最小代价和达到这个代价的 x 至少是多少即可。

这个容易 dp 求，设 dp_i 表示划分前 i 个数的最小代价（开成 pair 再记下最小段数），转移要么不选 \ge s 的段（此时显然划分成长度为 1 的段即可），要么选最近的点 j 使得 [j,i] 的和 \ge s 转移过来，给每个 i 预处理出来这个 j 即可。

时间复杂度 O(n\log^2n)。

代码。

某次模拟赛的 T4

嗯，强而有力啊。

这个猜一下就知道是凸的，写一个暴力的背包打表验证下是容易的。

然后上一个 wqs 二分，相当于给 [l,r] 内的数全减去 mid 之后要选若干个不相邻的数让和最大。

突然发现这个 check 起来好像很困难啊，其实是可以的。

具体来说，我们建一棵线段树，考虑给线段树上的每个结点预处理出来四个凸壳，凸壳上的第 x 个点表示区间内左右端点选/不选时选 x 个不相邻 a_i 的和最大是多少。注意到合并两个儿子的凸壳可以直接闵可夫斯基和（唉草这好像是下面才要写的东西）做到线性，所以说这个线段树的预处理是 O(n\log n) 的，没有问题。

wqs 二分后，我们拉出来线段树上的 \log 个结点，然后顺次做一个 dp，大概就是记 dp_{i,0/1} 表示考虑了前 i 个结点的区间且最后位置选/不选时的和最大是多少，对于第 i 个段发现我们只需要求出 x 使得原来当前段选 x 个的答案减去 x\times mid 最大就好了，可以在我们原来预处理的凸壳上二分或者开李超树。

这样每次 check 需要两个 \log，带上 wqs 二分的 \log 就是 O(q\log^3 n) 的了，好像卡下常就过了的样子。

使用整体 wqs 二分再加一点厉害的东西好像能做到 2\log，但我不会，有人会的话可以给我提一下。

代码没写，十分抱歉。

闵可夫斯基和

闵可夫斯基和的定义其实是对于两个点集 A,B 的，它们的闵可夫斯基和为点集 C=\{a+b|a\in A,b\in B\}。

对于普通的两个点集我们好像看不出来啥，那如果 A 和 B 是两个凸包呢？还是得偷下那张经典图。

这是两个凸包，考虑对它们做闵可夫斯基和，新的点集应该是这样的：

看上去新形成的点集没有什么特别之处。

但是如果我们关注新点集形成的凸包呢？注意第二张图最外边的一层边，就是新的凸包。

把边看作向量的话，你会发现每个向量都在原来的两个凸包中出现过，而且原来两个凸包的向量都各正好出现一次。

结论非常厉害，新凸包的边就是把原来两个凸包的边按照斜率排序后顺次拼接形成的。

这是对于全凸包来说的，对于凸壳也是同样的道理，也就是凸壳做闵可夫斯基和后新凸壳也是原凸壳的边排序后连成的。

在 OI 中我们关心的一般都是做闵可夫斯基和后新点集的凸包/凸壳，所以下文默认闵可夫斯基和的结果是一个凸包/凸壳。

这个能帮助我们做什么呢？

假设我们有两个下凸壳 f 和 g，我们要对它们做闵可夫斯基和。我们考虑到 OI 中一般考虑的是函数在每个非负整数位置的取值，所以凸壳上边的斜率可以定义为它们的差分数组。而注意到两个凸壳的差分数组都是单调的，所以说求出新的凸壳只需要把这两个有序的差分数组进行一个归并，再前缀和回去即可。也就是说我们可以以 O(|f|+|g|) 的时间求出它们的闵可夫斯基和。

是不是还不太清楚有什么用。我们考虑定义 h_i=\min_{j+k=i}(f_j+g_k)，也就是 f 和 g 的 (\min,+) 卷积，因为 f,g 都是下凸壳，所以 h 数组其实就是先求出 f,g 做闵可夫斯基和后的整个点集，然后每个横坐标取最低的点，那形成的不就是闵可夫斯基和后的下凸壳吗？也就是说，对两个下凸的数组做 (\min,+) 卷积只需要线性的时间，同理对两个上凸的数组做 (\max,+) 卷积也是线性的！

来个代码演示理解一下。

using poly = vector<int>;
poly convolution(const poly &a, const poly &b){  //对两个下凸的数组 a,b 做 (min,+) 卷积
    poly c; c.push_back(a[0] + b[0]);
    int l = 1, r = 1;
    while(l < a.size() && r < b.size()){
        if(a[l] - a[l - 1] < b[r] - b[r - 1]) c.push_back(a[l] - a[l - 1]), l++;
        else c.push_back(b[r] - b[r - 1]), r++;
    }
    while(l < a.size()) c.push_back(a[l] - a[l - 1]), l++;
    while(r < b.size()) c.push_back(b[r] - b[r - 1]), r++;
    For(i, 1, (int)c.size() - 1) c[i] += c[i - 1];
    return c;
}

所以，对于一类转移形如 (\max/\min,+) 卷积的 dp，验证了凸性之后往往可以使用闵可夫斯基和来优化。

Gym103202L Forged in the Barrens

题目链接

设 f_{i,j} 表示前 i 段已经划分出了 j 段的最大价值和，枚举上一段从哪里结束转移好像是 O(n^3) 的。

一个段内的极差可以理解成选两个数相减的最大值，所以我们可以修改一下状态的定义，改记 f_{i,j,0/1/2} 表示考虑了前 i 个数已经划分成了 j 段，当前段有负贡献/没有贡献/有正贡献的最大价值，这样就能 O(1) 转移从而做到 O(n^2) 了。

然后你发现好像就到此卡住了，不过如果你把 f_{n,*} 的表打出来就一定能发现这个题的答案关于 k 是凸的。

然后这里就有一个小技巧了，这种序列上的凸 dp 我们可以改写成区间 dp 的形式，这样转移就会带上一个凸壳合并的过程，从而优化。

设 f_{l,r,0/1/2,0/1/2,k} 表示考虑区间 [l,r] 划分成 k 段，两个 0/1/2 分别表示最左/右两段有负贡献/没有贡献/有正贡献时的最大价值。

转移时，考虑任取一个 mid\in[l,r]，写出来转移式子：

f_{l,r,sl,sr,k}=\max \begin{cases} \max(f_{l,mid,sl,sr,k},f_{mid+1,r,sl,sr,k})\\ \max_{x+y=k}(f_{l,mid,sl,1,x}+f_{mid+1,r,1,sr,y})\\ \max_{x+y+1=k}(f_{l,mid,sl,0,x}+f_{mid+1,r,2,sr,y})\\ \max_{x+y+1=k}(f_{l,mid,sl,2,x}+f_{mid+1,r,0,sr,y}) \end{cases}

每次转移直接把左右区间拉出来做三次 (\max,+) 卷积即可，这样一次转移的复杂度就是区间长度。

如果 mid 直接取在中点，就会形成一个类似线段树的分治结构，总复杂度是 O(n\log n) 的。

代码。

ABC383G Bar Cover

题目链接。

令 b_i=\sum_{j=i}^{i+k-1}a_j，将问题转化成，在 b 序列中选若干个数，选的数中间至少隔了 k-1 个数，求被选的数的和最大值。

不再说明答案关于选择的数个数是上凸的了。有了上一题的铺垫，我们直接设 f_{l,r,l_1,l_2,x} 表示考虑区间 [l,r]，左边空了大于等于 l_1 个数且右边空了大于等于 l_2 个数，区间内选了 x 数的答案。

转移时，枚举左区间的右半部分至少空了几个，设为 t，那么将 f_{l,mid,l_1,t} 和 f_{mid+1,r,k-1-t,l_2} 做 (\max,+) 卷积后即可转移到 f_{l,r,l_1,l_2}。

注意到每一层分治都要枚举 l_1,l_2,t 三个量，此时复杂度是 O(nk^3\log n) 的，难以通过。

加点剪枝，对于长度不超过 k 的区间显然只能选至多一个数，直接做 rmq 来求出 dp 值。

此时分治树上只有 \lfloor\frac{n}{k}\rfloor 个叶子，而分治树的结点个数显然与叶子个数同阶，所以这时候复杂度其实降到了 O(nk^2\log n)，能过。

代码。

Gym104128H Factories Once More

题目链接。

已经知道了闵可夫斯基和是差分归并，有些题目还会对差分数组整体做些额外的操作，这时候可能就需要些数据结构维护。

常见的维护手段是 dsu on tree 配平衡树，或者可并堆。

先考虑个暴力的树背包，设 f_{u,i} 表示在 u 子树内选 i 个点的最大答案，转移时考虑统计每一条边会被跨过几次，具体地我们记 w 为 u 到某个儿子 v 的边权，把儿子 v 合并过来时：

f'_{u,x}=\max_{i+j=x}(f_{u,i}+f_{v,j}+wj(k-j))

发现 wj(k-j)=-wj^2+wkj，是个关于 j 的开口向下的二次函数，而我们每次转移形如 (\max,+) 卷积，所以可以归纳说明我们这个背包是上凸的。所以每次做背包合并时，需要支持给儿子整体加上 wj(k-j)，并把差分数组归并。

首先考虑 wj(k-j) 对差分数组的影响，记 f(x)=-wx^2+wkx，那么 f'(x)=-2wx+wk，所以差分数组会整体加上一个一次函数。在树上直接归并差分数组复杂度是错的，考虑使用平衡树这种本身就有序的数据结构维护差分数组，给儿子的平衡树打个整体加一次函数的 Tag 然后直接 dsu on tree 插入即可，复杂度 O(n\log^2 n)。

实现时，为了避免不必要的麻烦可以不插入始终为 0 的 f_{u,0}。注意给平衡树加个垃圾回收，不然空间复杂度好像会多个 \log。

代码。

P9962 [THUPC 2024 初赛] 一棵树

题目链接。

交给洛谷审核的题解，可能讲得更详细。

其实和上一题基本是一样的。

同样考虑树背包统计每一条边的贡献，设 f_{u,x} 表示 u 子树内有 x 个黑点时的答案。

合并儿子 v 时，有 f'_{u,x}=\min_{i+j=x}(f_{u,i}+f_{v,j}+|k-2j|)，也就是和 f_{v,x}+|k-2x| 做 (\min,+) 卷积。

发现 |k-2x| 这个函数是下凸的，所以这个背包是下凸的，没问题。

记 d 为 |k-2x| 的差分数组，不难发现 i\le\lfloor\frac{k}{2}\rfloor 时 d_i=-2，i>\lceil\frac{k}{2}\rceil 时 d_i=2，而如果 k 为奇数中间还有个 0。

发现只需要支持前缀 -2 后缀 +2，可以像上题一样使用平衡树和 dsu on tree 做到 O(n\log ^2 n)。

当然因为这题对差分数组进行操作的范围是固定的，所以还可以使用可并对顶堆来实现，而且复杂度是 O(n\log n)，但是我还是实现了前者，因为我不太会对顶堆，最后还卡了半天常。

同样因为发现 f_{u,0}=(sz_u-1)\times k，所以也没必要插到平衡树里，可以少一些讨论。

不过这题确实稍微难写一点，因为要同时写按权值分裂和按大小分裂的 split。

代码。

slope trick

一般用于优化呈分段一次函数的 dp，同时也要求是凸的。

因为是凸的，所以每个点和下一个点连线的斜率是单调的，我们可以尝试使用数据结构维护所有斜率变化的点，扔进去一个点就表示图像在这个点往后的位置斜率就增加 1，同样重复扔多次就代表这个点往后斜率增加了不止 1，这也就要求了斜率的变化不能太大。

下文中，“斜率为 k 的拐点”默认意思是指这个拐点后面的直线斜率为 k。

常见的做法是考虑我们每一步 dp 转移到底在干什么，以及会对整个图像的斜率产生什么影响。

至于维护出了斜率后如何求出答案，可能要分不同的题目来讨论，有时我们可以根据某个容易算的初值然后遍历这些拐点，有时维护拐点的过程我们能直接找到 dp 的决策点。

用例题来简单感受一下。

CF713C Sonya and Problem Wihtout a Legend 加强

题目链接。

首先每个数减去它的下标变成单调不降，然后只会填原来出现过的数。

所以考虑一个朴素的 dp：设 dp_{i,j} 表示考虑前 i 个数且最后 a_i 被调到了 j 的最小花费。

转移是容易的，dp_{i,j}=\min_{k=1}^j(dp_{i-1,k}+|a_i-j|)，直接实现就是 O(n^2) 的，因为第二维只有原来出现过的数是有用的。

设函数 f_i(x)=dp_{i,x}，因为每次 dp 转移都只有取 \min 和加绝对值函数这种操作，我们可以通过归纳说明 f_i(x) 就是我们上面提到的分段一次函数，同时满足凸性（本题为下凸）。

按照上面提到的，对这种凸的分段一次函数尝试维护出它的所有斜率拐点。先做进一步的转化，我们考虑 f_i(x) 是怎么转移到 f_{i+1}(x) 的：令 f'_{i}(x)=\min_{j\le x}f_i(j)，也就是做一个前缀 \min，再给 f'_i(x) 整体加上 |a_i-x|，我们就得到了 f_{i+1}(x)。

假设已经得到了 f_i(x) 的斜率拐点集合 S，分别考虑前缀 \min 和加绝对值函数两种操作：

上面的部分可以仔细画图理解下，还是很直观的。根据上述分析，只需要用一个大根堆维护所有斜率 \le0 的拐点即可。

本题 dp 的决策点一定可以取斜率为 0 的那个拐点，所以统计答案很方便，最后的复杂度是 O(n\log n)。

代码。

CF372C Watching Fireworks is Fun 加强

题目链接。

当时被放在了模拟赛 T1，被狠狠薄纱了。

容易发现 \sum b_i 一定会被统计到答案，所以我们只需要最小化 \sum|a_i-x| 即可。

考虑设 dp_{i,x} 表示第 i 个烟花放出来时在位置 x 的答案。

转移形式很简单，记 \Delta t=t_i-t_{i-1}：

dp_{i,x}=\min_{y\in[x-\Delta t\times d,x+\Delta t\times d]}dp_{i-1,y}+|a_i-x|

我们仿照上一题的思想，将转移的操作分开来看。首先我们令 dp'_x=\min_{y\in[x-\Delta t\times d,x+\Delta t\times d]} dp_{i,y}，也就是找到能走到当前位置的 dp 值的最小值，然后再对 dp'_x 整体加上 a_i-x，就得到了 dp_{i+1,x}。显然 dp 转移由取 \min 和加一个下凸的 |a_i-x| 两种操作构成，所以 dp 数组本身是下凸的分段一次函数。

然后我们就要考虑这些操作对斜率的影响了。

对于第一个向周围 \Delta t\times d 的邻域内取 \min 的操作，其实就是对拐点进行平移。具体来说对于斜率 \le 0 的部分因为是单调不升的所以会和右侧的部分取 \min，也就是斜率 \le 0 的拐点向左平移 \Delta t\times d 个单位，而斜率 >0 的部分因为是单调增的所以会和左边取 \min，因此斜率 >0 的拐点会向右平移 \Delta t\times d 个单位。

然后就是加 |a_i-x| 了，这个就非常简单了，直接把斜率为 0 的拐点和 a_i 的位置关系讨论下就可以了，具体来说假设斜率为 0 的拐点位置为 l，斜率为 1 的拐点位置为 r（体现在图像上，[l,r] 就是函数取到最小值的那个区间）：

直接开两个堆分别维护斜率 \le 0 和 >0 的拐点，平移可以直接维护两个加法标记，加入 a_i 拐点时取出两个堆顶按照上面的讨论维护即可，值得一提的是@崔化博 场上切掉了这一题但是写了棵平衡树来维护。

至于统计答案，可以直接实时维护整个函数的最小值，还是比较方便的。

时间复杂度 O(m\log n)。

代码。

P3642 [APIO2016] 烟火表演

题目链接。

仍然使用朴素的 dp，设 f_{u,x} 表示令 u 子树内的叶子到 u 的距离为 x 需要的最小代价，记 w(u,v) 为边 (u,v) 的边权：

f_{u,x}=\sum_{v\in son(u)}\min_{i+j=x}(f_{v,i}+|w(u,v)-j|)

观察下形式，发现 f_{u,x} 就是每个 f_{v,x} 和函数 |w(u,v)-x| 做 (\min,+) 卷积后相加。

显然 f_{u,x} 是下凸的：|w-x| 本身下凸，和它做 (\min,+) 卷积后下凸，若干个下凸的函数加起来还是下凸。

虽然转移时儿子要和函数 |w(u,v)-x| 做闵可夫斯基和，但是本题我们显然不能直接维护差分数组，因为第二维的值域太大了，但是我们显然可以把它描述成一个分段的一次函数，所以我们考虑维护斜率的拐点。

其实上面也提到过斜率就是差分，那 slope trick 实质上维护的就是差分数组发生变化的点是不是，联系性还是很强的。

考虑 f_{v,x} 和 |w-x| 做闵可夫斯基和后图像的变化，我们可以在坐标系上模拟一下闵可夫斯基和的过程（按照斜率排序顺次相连），记 l,r 分别为原来 f_{v,x} 斜率为 0 和斜率为 1 的拐点（即原来 f_{v,x} 在 [l,r] 内取到最小值）：

  1. 当 x<l 时，函数图像整体向上平移 w 格。
  2. 当 l\le x<l+w 时，这一段会变成一条新的斜率为 -1 的折线。
  3. 当 l+w\le x\le r+w 时，这一段会对应原来的 [l,r]，也就是原来平的那一部分会向右平移 w 格。
  4. 当 x>r+w 时，这一侧会多一个无限长的斜率为 1 的直线。

求出每个 f_{v,x} 和 |w-x| 做闵可夫斯基和之后的结果，把它们相加起来就得到了 f_{u,x}，而相加就是直接把拐点合并起来。

所以维护流程大概是这样的：给树上每个结点开一个可并堆维护所有的斜率拐点，把每个儿子的拐点直接全部合并到自己的堆里，同时再考虑父亲到自己的边的 |w-x| 对自己拐点的影响，处理掉之后等待合并到父亲的堆内。

处理父亲的 |w-x| 对自己拐点的影响时，直接把斜率大于 1 的拐点全都弹掉（我们注意到这个流程里我们其实不关心斜率 >1 的拐点，它们是完全没用的），然后取出堆顶的两个点（也就是 l,r），把 l+w,r+w 重新扔进堆里即可。

时间复杂度 O(n\log n)，我的代码里使用了 pbds 的可并堆，我并不会写左偏树。

代码。

终于写完了，可以和这个大坑告一段落了！！

其实这里本来应该还有一道 AGC069A 的，但是那题的难点感觉其实不在 slope trick 上，所以删去了。