凸优化：k-子段和系列问题

FLY_lai · 2025-02-26 14:23:53 · 算法·理论

给定长度 n 的序列 a_1\sim a_n。

问题 1：给定固定的 k，选 k 个不相交的子段，和最大是多少。

问题 2：支持两种操作，全局加和查询区间最大子段和，允许离线。

问题 3：对 k=1\sim n，求选 k 个不相交的子段，和最大分别是多少。

问题 4：询问 q 次，每次询问从一个区间选 k 个不相交的子段，和最大是多少。

问题 1

法一：使用 WQS 二分。dp[i] 表示前 i 个数任意分段，每多一段就多 -x 的最大收益。dp[i]=\max(dp[i-1],\max_j(dp[j]+s[i]-s[j-1]))，拆一下式子即可。复杂度 O(n\log V)。

法二：模拟费用流。线段树支持查询最大子段和即可。复杂度 O(k\log n)。

问题 2

本题即 P5073 世上最幸福的女孩

离线操作。把全局加 k 的操作删除，转而给第二种操作升维：(l,r,k) 表示询问 a_l+k,a_{l+1}+k,\dots,a_{r}+k 的最大子段和。

考虑用线段树处理这个问题。最大子段和总共需要四个信息：最大前缀和、最大后缀和、区间总和、最大子段和。

1. 区间总和。这是好求的，对于参数 (l,r,k)，其区间总和是 \sum_{i=l}^{r}a_i+k=s_r-s_{l-1}+k\times (r-l+1)。

2. 最大后缀和。这和最大前缀和类似。

3. 最大前缀和。

   先考虑对一个结点怎么求。

   在结点 [l,r] 上，用 (i,f_i) 表示 a_{l\sim r} 有一个长度 i 的前缀，其和为 f_i，则对于 (l,r,k)，最大前缀和就是 \max\{i\cdot k+f_i\}，容易发现这只会取到 (i,f_i) 的上凸壳。如果能预先求出上凸壳，就可以二分求最大前缀了。

   怎么求上凸壳？先求左右儿子的上凸壳，给右边的凸壳向上平移左边的总和（这显然还是个凸壳），然后利用闵可夫斯基和线性合并。一共 O(\log n) 层，每层都是线性合并，预处理凸壳复杂度 O(n\log n)。

   现在知道怎么对于一个结点求它的最大前缀和了，多个结点时按顺序合并即可。

4. 最大子段和。

   有了前后缀，最大子段和也很简单了。先递归左右儿子，先取左右儿子的最大子段和，然后用左儿子的最大后缀和右儿子的最大前缀拼起来。

把询问区间拆成 O(\log n) 个线段树结点即可。

但如果这样子做是 O(n\log^2 n) 的，或许其他题可以过，但是 Ynoi 的题还是给予足够的尊重吧。我们要优化到 O(n\log n)。我们发现，如果把这些询问再离线一次，把所有询问按 k 排序，每个凸壳的最优决策点是单调向右的，用指针即可解决。复杂度 O(n\log n)。

但是这样做还是通过不了本题。因为空间复杂度是 O(n\log n) 的。瓶颈在于需要把所有凸包在对应结点都存下来。如果能每次只存一层的凸包就好了。一个想法是把所有询问记录到每个对它生效的结点上，在结点处处理所有涉及它的询问，然后不保存它的空间。然而这样凸包的复杂度少了，但是把询问拆出来的复杂度变成 O(m\log n) 了。 但这给了我们启发，我们直接带着所有询问向下递归，判断该询问在该区间是否生效，是否下放到左右儿子即可（下放后要释放空间或是直接使用单链表移过去下放！），这样每个时刻每个询问至多只会在两个节点上。空间复杂度 O(n+m)。

问题 3

法 0.5：WQS 二分。复杂度 O(n^2\log n)。

法一：模拟费用流。复杂度 O(n\log n)，每多流一个就是更大的答案。

法二：凸优化 DP。

闵和、凸优化常和分治/区间 DP 搭配，因为凸壳合并可以线性，分治 \log n 层，总复杂度就是 O(n\log n) 的。本题是一个例子。