【前置知识】

convex 与 concave：这是对于数组的概念。类比函数，下凸就是 convex，上凸就是 concave。

【<min,+>卷积问题】

考虑两个数组 \(a_{1\sim n},b_{1\sim m}\)，定义它们的<min,+>卷积结果 \(c\)：

1. \(|c|=n+m\)。

2. \(c_i=\min_{j+k=i}\{a_j+b_k\}\)。

因为普通的卷积是 \(\sum +\)，形式类似。所以这种运算就叫做<min,+>卷积。<max,+>卷积的定义是类似的。

这个问题目前没有快于 \(O(nm)\) 的解法，但是在特殊情况下可以做一些优化。

【双 convex 情况】

结论：如果 \(a,b\) 都 convex，可以 \(O(n+m)\) 解决这个问题。

考虑 \(a,b\) 的差分数组 \(\Delta a,\Delta b\)。（\(\Delta a_1=a_1\)，\(\Delta a_i=a_i-a_{i-1}\)）
则 \(c_i\) 就是在 \(\Delta a,\Delta b\) 中最小的 \(i\) 个数之和。

容易证明，不再赘述。

【单 convex 情况】

结论：如果 \(a\) 是任意数组，\(b\) 是 convex 的，可以做到 \(O(n\log m)\) 解决。

这个情况比上面的复杂很多。我们先定义一下两个函数方便叙述。

观察 1：\(c_i\) 实际上等于 \(x=i\) 处，\(f_{1\sim n}(x)\) 最低点的值。
观察 2：\(f_j(x)\) 是 \(f(x)\) 的平移。

于是求 \(c\) 数组，实际上等价于求 \(f_{1\sim n}(x)\) 的下凸壳。下面讲解怎么求。

由观察 2 知 \(f_j(x)\) 与 \(f_{j'}(x)\) 最多一个交点（\(j\neq j'\) 时）。有了这个观察能做什么？

其实这里已经可以用李超线段树做了，不过李超树是 \(O(n\log^2 n)\) 的，我们像四边形不等式的队列那样，进一步优化。

维护队列 \(q\) 保存 \(i_1,i_2,\dots,i_k\)，表示当前还有用的函数图像有 \(f_{i_1\sim i_k}(x)\)。现加入 \(f_j(x)\)。若 \(f_j(x)\) 与 \(f_{i_k}(x)\) 的交点在 \(f_{i_k}(x)\) 与 \(f_{i_{k-1}}(x)\) 的交点左侧，则 \(i_k\) 没有用了，可以弹出。进行完所有弹出后，假设此时队列末尾元素为 \(k\)（如果队列弹空了就直接加入 \(j\)）。在 \(f_k(x)\) 有用的区间内二分，找到第一个 \(f_k(x)\le f_j(x)\) 的位置 \(pos\)。从 \(pos\) 往后，\(f_k(x)\le f_j(x)\)。

在具体实现时，除了记录 \(i_1\)，还要记录它的有用区间 \([l_{i_1},r_{i_1}]\)。这和四边形不等式的二分队列是一样的。

二分带一个 \(\log m\)，而函数个数是 \(n\)，所以总复杂度是 \(O(n\log m)\) 的。

【背包优化】

【01 背包优化】

记总重量为 \(C\)，重量种类数为 \(m\)，这里给出一个 \(O(n\log n+mC\log C)\) 的做法。

把物品按重量从大到小排序，同重量按价值从大到小排序。

令 \(A_i[j]\) 表示考虑完前 \(i\) 种重量后，选一些物品总重为 \(j\) 的最大价值。

从 \(A_{i-1}\) 怎么推到 \(A_i\)？设第 \(i\) 类重量为 \(w\)。用 \(B[k]\) 表示在第 \(i\) 类中选总重为 \(kw\) 的物品（其实就是选 \(k\) 个）的最大价值。

观察发现 \(B[k]\) 是 concave 的。因为 \(B[k+1]\) 比 \(B[k]\) 选多一个物品，而且这多的一个物品必然是价值第 \(k+1\) 大的物品。再多选一个，就是第 \(k+2\) 大的了。以此类推，增长的价值必然递减。

把 \(A_{i-1}[j]\) 按 \(j\bmod w\) 的余数分类，每一类单独与 \(B\) 做<max,+>卷积，就能得到对应位置的 \(A_{i}[j]\)。每一类 \(A\) 的长度是 \(\dfrac{C}{w}\)，\(B\) 的长度是 \(w\)，一共做 \(w\) 次（余数分 \(w\) 类）。所以复杂度是 \(O(\dfrac{C}{w}\log w\cdot w)=O(C\log w)=O(C\log C)\)。

注意这里不能直接把 \(B\) 拓展到长度为 \(C\) 的数组，然后拿这个拓展后的数组卷。因为拓展后 \(B\) 显然就不 concave 了。

一共 \(m\) 种重量，所以复杂度是 \(O(mC\log C)\)。排序还有 \(O(n\log n)\)。总复杂度 \(O(n\log n+mC\log C)\)。

【完全背包优化】

这个优化和<max,+>卷积凸优化没关系。

设最大重量为 \(D\)，总重 \(C\)，给出一个 \(O(D^2\log C)\) 的解法。基于倍增。

令 \(ans_i\) 表示总重为 \(i\) 时的最大价值。暴力求出 \(ans_{0}\sim ans_{2D}\)，复杂度 \(O(D^2)\)。

有：当 \(i>D\)，\(ans_i=\max_{|j-k|\le D,j+k=i}(ans_j+ans_k)\)。

进而可以得到：\(ans_{j-D/2\sim j+D/2}\) 和 \(ans_{k-D/2\sim k+D/2}\) 做一次<max,+>卷积可以得到 \(ans_{j+k-D\sim j+k+D}\)。我们只需要 \(O(D^2)\) 的来做这个就够了。

既然 \(O(D^2)\) 可以从 \(j,k\rightarrow j+k\)，那么直接倍增就可以做到 \(O(D^2\log C)\)。