凸函数相关问题
基础知识
- 一个函数$f$是上凸函数，当且仅当对于任意$a\lt c$，记录$b=(a+c)/2$，有$2f(b)\geq f(a)+f(c)$。
- 一个函数$f$是下凸函数，当且仅当对于任意$a\lt c$，记录$b=(a+c)/2$，有$2f(b)\leq f(a)+f(c)$。
- 如果函数$f$在定义域上二次可微，且$f''\geq 0$，则$f$是下凸函数，若$f''\leq 0$，则$f$是上凸函数。
- 函数$a^x$是下凸函数，如果$a\geq 0$。
- 函数$\ln x$是上凸函数，$\exp(x)$是下凸函数。
- 函数$x^n$在$[0,+\infty)$上，若$0\leq n\leq 1$,则为上凸函数，若$x\geq 1$，则为下凸函数。
命题1：如果函数$f$和函数$g$都是上凸（下凸）函数，则它们的和$f+g$也是上凸（下凸）函数。
证明：略。
命题2：如果函数$f$和函数$g$都是上凸函数，则它们的和$\min(f,g)$也是上凸函数。
证明：略。
命题3：如果函数$f$和函数$g$都是下凸函数，则它们的和$\max(f,g)$也是下凸函数。
证明：略。
命题4：如果函数$f$，$g$是上凸（下凸）函数，且$f$递增，则$f(g)$也是上凸（下凸）函数。
证明：略。
最大和问题
题目1：给定$m$个线性函数$f_1,\ldots,f_m$，其中$f_i(x)=a_ix+b_i$，现在我们希望为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值，且要求满足$\max_{i=1}^mx_i=n$，在满足约束条件下，要求$\sum_{i=1}^nf_i(x_i)$尽可能大。
我们可以这样来理解这个问题，首先我们有$m$个可投资对象和$n$个资源，且已经获利$\sum_{i=1}^mb_i$，接下来如果我们为第$i$个可投资对象每投入一单位资源，那么就能获利$a_i$，问最大获利多少。
这个自然是将所有资源都砸在$a_i$最大的可投资对象上了。
题目2：给定$m$个函数$f_1,\ldots,f_m$，且每个函数的成像都构成一个上凸包，现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值，且要求满足$\sum_{i=1}^mx_i=n$，在满足约束条件下，要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m,n\leq 10^5$
利用题目1的方式，我们来试图重新解读问题。首先我们有$m$个可投资对象和$n$个资源，且已经获利$\sum_{i=1}^mf_i(0)$，接下来如果我们为第$i$个可投资对象每投入一单位资源，那么就能获利$f_i(x+1)-f_i(x)$（$x$是已经向第$i$个可投资对象投入的资源总量），问最大获利多少。
我们会发现由于所有的函数都是上凸包，因此对于任意$i$，$d_i(x+1)=f_i(x+1)-f_i(x)$是非严格递减函数。考虑到$d_i(1)\geq d_i(2)\geq \ldots$，因此在最终结果中，如果选择$d_i(x+1)$那么我们必定也会选择$d_i(x)$，因此我们可以将所有可选的收益一开始就全部展开${d_i(x)}$，现在我们要做的就是从$d_i(x)$中选择正好$n$个元素，且元素之和最大。这个步骤自然我们会选择使用贪心算法来完成。
现在回到问题，如果我们把所有方案都展开，那么可能会有$nm$个选择，这样太多了，但是由于我们在取得$d_i(x)$之前是不会考虑$d_i(x+1)$的，因此我们可以对每个$i$，仅考虑$x$最小且未被选择的$d_i(x)$。实际操作中，我们只需要维护一个大小为$m$的大根堆即可，当我们将$d_i(x)$弹出的同时，将$d_i(x+1)$加回即可，总的时间复杂度为$O(n\log_2m)$。
提供一道SGU的问题。
题目3：给定$m$个函数$f_1,\ldots,f_m$，且每个函数的成像都构成一个上凸包，现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值，且要求满足$\sum_{i=1}^mx_i=n$，在满足约束条件下，要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m\leq 10^5$,$1\leq n\leq 10^{18}$
这个问题是今天比赛的一道题目学到的。由于是上凸包，因此我们可以用三分算法为每个函数找到其极值点（在非负整数定义域下），记$f_i$的极值点在$p_i$处取到。
分两种情况讨论，如果$n\leq \sum_{i=1}^m p_i$，那么我们可以断定一定有$x_i\leq p_i$，否则对应的就有$x_i\geq p_i$。
如果是$n\leq \sum_{i=1}^m p_i$的情况。记$d_i(x)=f_i(x)-f_i(x-1)$称为函数$f_i$在点$x$处的增量。很显然最优解中，采用的最小增量一定是最大的，我们可以通过二分法找到这个最小增量，这里的时间复杂度为$O(n(\log_2M)^2)$，其中$M$是数据范围。找到最小增量$\delta$后，我们将$x_i$设置为$f_i$增量大于等于$\delta$的整数点数目（不包括0）。那么此时可能会有$\sum_{i=1}^mx_i>n$的情况出现，我们可以保证所有函数增量大于$\delta$的整数点都会被保留（否则为什么要使用增量为$\delta$的点呢？），而增量为$\delta$的点可以删除一部分，来满足$\sum_{i=1}^mx_i>n$，这一部分的时间复杂度为$O(m)$。
对于$n\geq \sum_{i=1}^m p_i$的情况，与上面的方法类似。
最后总的时间复杂度为$O(m(\log_2M)^2)$。
提供一道题目。
题目4：给定$n$个非严格递增数组$a_1,a_2,\ldots,a_n$，长度分别为$t_1,\ldots,t_n$。之后要求执行正好$m$次操作，每次操作选择一个非空的数组头，并且删除数组头部元素。要求$m$次操作后删除的元素总和最大。输入满足$1\leq n,m\leq 3000$，且$m\leq \sum_{i=1}^nt_i\leq 10^6$，每个数组元素在$0$到$10^9$之间。
一般的DP做法时间复杂度为$O(nm\sum_{i=1}^nt_i)$，太慢了。
很显然我们最多只会有一个数组的元素是部分取走的。因此就得出了我们的思路，一种预处理前后缀的做法的时间复杂度为$O(nm^2+\sum_{i=1}^nt_i)$，还是不够好。
这里我们可以神奇的套上分治。类似与并行二分，我们可以将要处理的数组分为两部分，之后在左边的数组上暴力计算DP，并在递归处理右部分的时候作为初始值下传。可以发现抵达叶子（区间只有一个元素）的时候，这时候其余元素都被处理到了。
树的每一层的时间复杂度都是$O(nm)$，最后一层的时间复杂度为$O(\sum_{i=1}^n t_i)$。因此总的时间复杂度为$O(nm\log_2n + \sum_{i=1}^nt_i)$。
提供一道题目。
并且由于背包问题中交换商品顺序不影响结果，因此可以用可撤销队列来做，时间复杂度也是$O(nm\log_2n + \sum_{i=1}^nt_i)$。
题目5：给定$m$个函数$f_1,\ldots,f_m$，且每个函数的成像都构成一个上凸包，且每个函数的值域都是正数，现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值，且要求满足$\sum_{i=1}^mx_i=n$，在满足约束条件下，要求$\prod_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m\leq 10^5$,$1\leq n\leq 10^{18}$。输出最大可能的乘积，结果对$P$取模。
我们希望$\prod_{i=1}^nf_i(x_i)$最大，等价于希望$\sum_{i=1}^n\ln f_i(x_i)$最大。考虑到$\ln f_i$也是个上凸包，因此我们可以用问题3的方式找到每个函数的赋值方案，之后算出真实的乘积即可。时间复杂度为$O(n\log_2m\log_2M)$。