Wqs Binary Search

$$
f^*(x^*) = \sup_{x\in\mathbf R^d}x^*\cdot x - f(x).
$$

$$
y = k\cdot x + b.
$$

也就是说，本文不会涉��平行于 $y$ 轴的超平面．为表述方便，本文并不严谨地将 $k$ 称为该超平面的「斜率向量」，$b$ 称为该超平面的「截距」．将这一超平面的方程写成更标准的形式，就是

$$
k\cdot x - y = -b.
$$

它的一个法向量是 $(k,-1)$．因此，所谓的斜率向量其实是将超平面的法向量归一化使得它的最后一个分量等于 $-1$ 时，所得到的法向量的前 $d$ 个分量．

1.  $f(x)$ 是正常凸函数且 [下半连续](https://en.wikipedia.org/wiki/Semi-continuity)，
2.  $f(x)\equiv+\infty$，或
3.  $f(x)\equiv-\infty$．

对于非正常函数的情形，可以验证 $f(x)\equiv+\infty$ 和 $f(x)\equiv-\infty$ 互为共轭．除此之外，只要 $f(x)$ 在任何一点处取到 $-\infty$，必然有 $f^*(x^*)\equiv+\infty$．所以，满足 $f^{**}=f$ 的非正常函数只有这两种情形．下面的讨论仅限于正常函数．对于正常函数，下半连续且凸的条件等价于它的上境图是闭凸集．

这一条件的必要性是容易的．因为 $f=f^{**}$ 是 $f^*$ 的凸共轭，作为一系列线性函数的上确界，它的上境图必然是一系列闭凸集的交集，所以必然是闭凸集．这就说明，满足 $f^{**}=f$ 的正常函数必然是下半连续且凸的．

反过来，这些条件也是充分的．和其他强对偶定理的证明一样，证明可以分为两步．

第一步，说明弱对偶成立，即 $f(x)\ge f^{**}(x)$．由凸共轭的定义可知，对于所有 $x,x^*\in\mathbf R^d$，都有

$$
f^*(x^*) \ge x^*\cdot x-f(x).
$$

这就说明，对于所有 $x,x^*\in\mathbf R^d$，同样有

$$
f(x) \ge x^*\cdot x-f^*(x^*).
$$

对不等式右侧中的 $x^*$ 取上确界，就有 $f(x)\ge f^{**}(x)$．

第二步，利用 [超平面分离定理](https://en.wikipedia.org/wiki/Hyperplane_separation_theorem) 说明 $f(x)\le f^{**}(x)$．假设不然，存在 $x_0\in\mathbf R^d$ 使得 $f(x_0)>f^{**}(x_0)$ 成立．因为 $f(x)$ 的上境图 $\operatorname{epi}(f)$ 是闭凸集，而且单点集 $\{(x_0,f^{**}(x_0))\}$ 是紧凸集，所以，根据超平面分离定理，存在 $(\lambda,t)\in\mathbf R^d\times\mathbf R$ 和 $\alpha\in\mathbf R$ 使得对于所有 $x\in\operatorname{dom} f:=\{x\in\mathbf R^d:f(x)<+\infty\}$ 和所有 $y\ge f(x)$ 都有

$$
\lambda\cdot x-ty <\alpha <\lambda\cdot x_0 - tf^{**}(x_0)
$$

成立．因为 $y$ 可以选得任意大，所以必然有 $t\ge 0$．这又可以分为两种情形．

首先，讨论 $t>0$ 的情形．此时，将不等式的各部分都同除以 $t$，并设 $\lambda'=t^{-1}\lambda$ 和 $\alpha'=t^{-1}\alpha$，就得到

$$
\lambda'\cdot x-y < \alpha'< \lambda'\cdot x_0-f^{**}(x_0).
$$

对所有 $x\in\operatorname{dom} f$，令 $y=f(x)$，就都成立

$$
\alpha' > \lambda'\cdot x - f(x).
$$

故而，对不等号右侧的 $x$ 取上确界，有

$$
\alpha' \ge \sup_{x\in\mathbf R^d}\lambda'\cdot x - f(x) = f^*(\lambda').
$$

进而，有

$$
f^{**}(x_0) < \lambda'\cdot x_0-f^*(\lambda') \le \sup_{x^*\in\mathbf R^d}x^*\cdot x_0-f^*(x^*) = f^{**}(x_0).
$$

这一矛盾说明 $t>0$ 的情形并不成立．

最后，讨论 $t=0$ 的情形．事实上，将要说明的是，可以通过微扰，将它转化为 $t>0$ 的情形．任取 $\lambda_0\in\operatorname{dom}f^*$，根据凸共轭的定义可知，对于任何 $x\in\operatorname{dom}f$ 和 $y\ge f(x)$ 都有

$$
\lambda_0\cdot x-y\le f^*(\lambda_0).
$$

因此，对于任意 $\varepsilon>0$，都有

$$
(\lambda+\varepsilon\lambda_0)\cdot x - \varepsilon y<\alpha+\varepsilon f^*(\lambda_0).
$$

同时，因为 $\alpha<\lambda\cdot x_0$，所以，对于充分小的 $\varepsilon>0$，又有

$$
\alpha+\varepsilon f^*(\lambda_0) < (\lambda+\varepsilon\lambda_0)\cdot x_0 - \varepsilon f^{**}(x_0).
$$

因此，如果取 $\lambda'=\lambda+\varepsilon\lambda_0$，$t'=\varepsilon$ 和 $\alpha'=\alpha+\varepsilon f^*(\lambda_0)$，那么，就有

$$
\lambda'\cdot x-t'y <\alpha' <\lambda'\cdot x_0 - t'f^{**}(x_0).
$$

这就又回到了前一种情形，仍然会导致矛盾．

这一矛盾说明，并不存在满足 $f(x_0)>f^{**}(x_0)$ 的点 $x_0\in\mathbf R^d$．故而，总有 $f(x_0)\le f^{**}(x_0)$．

结合这两步证明的结果，就得到 $f^{**}(x)=f(x)$ 成立．

$$
f(x) \ge f(x_0)+x^*\cdot(x-x_0),
$$

那么，就称 $x^*$ 是 $f(x)$ 在 $x_0$ 处的一个 **次梯度**（subgradient）．函数 $f(x)$ 在 $x_0$ 处的全体次梯度的集合称为它在该处的 **次微分**（subdifferential），记作 $\partial f(x_0)$．

$$
x^*\in\partial f(x) \iff x^*\cdot x = f(x) + f^*(x^*).
$$

进而，如果 $f$ 还是下半连续的，那么这两个条件都等价于 $x\in\partial f^*(x^*)$．

$$
f(x') \ge f(x) + x^*\cdot(x'-x),~\forall x'\in\mathbf R^d.
$$

这等价于

$$
x^*\cdot x - f(x) \ge x^*\cdot x'-f(x'),~\forall x'\in\mathbf R^d.
$$

这又等价于

$$
x^*\cdot x - f(x) \ge \sup_{x'\in\mathbf R^d}x^*\cdot x'-f(x') = f^*(x^*).
$$

但是，依据凸共轭的定义，总是有

$$
x^*\cdot x - f(x) \le f^*(x^*).
$$

因此，前一式中的大于等于号实际上等价于等号，也就等价于下式

$$
x^*\cdot x = f(x) + f^*(x^*).
$$

这就完成了第一部分的证明．

对于 $f$ 是下半连续的正常凸函数的情形，依 Fenchel–Moreau 定理，有 $f^{**}=f$．因此，这两个条件等价于

$$
x^*\cdot x = f^*(x^*) + f^{**}(x).
$$

再次应用第一部分的结论，它们也就等价于 $x\in\partial f^*(x^*)$．

$$
\begin{aligned}
\partial f(x) &= \arg\max_{y^*\in\mathbf R^d} x\cdot y^* - f^*(y^*),\\
\partial f^*(x^*) &= \arg\max_{y\in\mathbf R^d} x^*\cdot y - f(y).
\end{aligned}
$$

按照凸共轭的定义，有

$$
f^*(x^*) = \sup_{y\in\mathbf R^d} x^*\cdot y - f(y),
$$

所以，

$$
x \in \arg\max_{y\in\mathbf R^d} x^*\cdot y - f(y)
$$

当且仅当 $f^*(x^*) = x^*\cdot x - f(x)$，而这一等式成立，又当且仅当 $x\in\partial f^*(x^*)$．这就证明了两个集合是相等的．

简言之，就是在长度为 $n$ 的链上，求解大小为 $m$ 的最大权独立集的问题．

1.  目标函数 $f(x,y)$ 是关于 $(x,y)$ 的凸函数；
2.  可行域映射 $y\mapsto\mathcal D(y)$ 的图像 $\{(x,y):x\in\mathcal D(y)\}$ 是凸集．

如果对于任意 $y\in\mathbf R^d$，都有 $v(y)>-\infty$，那么，价值函数 $v(y)$ 是关于 $y$ 的正常凸函数．

$$
v(\alpha y_1+(1-\alpha)y_2) \le \alpha v(y_1) + (1-\alpha) v(y_2).
$$

如果 $v(y_1)=+\infty$ 或 $v(y_2)=+\infty$，那么不等式的右侧就是 $+\infty$，不等式必然成立．否则，$v(y_1)$ 和 $v(y_2)$ 都是有限值．对于任意 $\varepsilon>0$ 和 $i=1,2$，都存在 $x_i\in\mathcal D(y_i)$ 使得 $f(x_i,y_i)< v(y_i)+\varepsilon$ 成立．利用映射 $\mathcal D$ 的图像的凸性可知

$$
\alpha x_1+(1-\alpha)x_2 \in \mathcal D(\alpha y_1+(1-\alpha)y_2).
$$

也就是说，$\alpha x_1+(1-\alpha)x_2$ 是参数为 $\alpha y_1+(1-\alpha)y_2$ 的最优化问题的一个可行解．利用最优化条件和目标函数的凸性可知

$$
\begin{aligned}
v(\alpha y_1+(1-\alpha)y_2)
&\le f(\alpha x_1+(1-\alpha)x_2,\alpha y_1+(1-\alpha)y_2) \\
&\le \alpha f(x_1,y_1) + (1-\alpha)f(x_2,y_2) \\
&< \alpha v(y_1) + (1-\alpha) v(y_2) + \varepsilon.
\end{aligned}
$$

因为 $\varepsilon$ 的选取是任意的，令 $\varepsilon\rightarrow 0$，就有

$$
v(\alpha y_1+(1-\alpha)y_2) \le \alpha v(y_1) + (1-\alpha) v(y_2).
$$

因此，价值函数 $v(y)$ 的凸性成立．

$$
v(y_1,y_2)=\min_{x\in\mathbf R^n} c\cdot x \text{ subject to }A_1x\le y_1,A_2x=y_2,x\ge 0.
$$

那么，价值函数 $v(y_1,y_2)$ 是关于 $(y_1,y_2)$ 的凸函数．

上文列举的那些图论问题，都可以写成一个 LP 问题而不需要施加整数约束；但对于其他的一些问题，例如一般图的最大独立集问题等，整数约束则是必要的．另外，即使一个图论问题可以写成 LP 的形式，在该问题引入额外的线性约束条件后，仍然可能会破坏相应的 ILP 问题和 LP 问题的等价性，从而这个带约束的图论问题不再能够写成线性规划的形式．

$$
\begin{aligned}
v(m)=\min_{\{f_{ij}\}}\;&\sum_{(i,j)\in E}w_{ij}f_{ij}\\
\text{subject to }&\sum_{(j,i)\in E}f_{ji} - \sum_{(i,j)\in E}f_{ij} = 
\begin{cases}
-m, & i=s,\\
m,  & i=t,\\
0,  & \text{otherwise},
\end{cases}
~\forall i\in V,\\
&0\le f_{ij}\le c_{ij},~\forall (i,j)\in E.
\end{aligned}
$$

因此，最小费用 $v(m)$ 是参数 $m$ 的凸函数．

-   从源点 $s$ 出发，向结点 $r$，连接一条容量为 $m$、费用为 $0$ 的边；
-   从结点 $r$ 出发，向每个奇数结点 $i=1,3,\cdots,2\lceil n/2\rceil-1$ 连接一条容量为 $1$、费用为 $0$ 的边；
-   从每个偶数结点 $i=0,2,\cdots,2\lfloor n/2\rfloor$ 出发，向汇点 $t$ 连接一条容量为 $1$、费用为 $0$ 的边；
-   对于每个 $i=1,\cdots,n$，从 $i-1$ 和 $i$ 中的奇数结点出发，向偶数结点连接一条容量为 $1$、费用为 $a_i$ 的边．

最终答案就是求得的最大费用．将这一图论模型转换为相应的线性规划问题（具体见上文推论的证明），那么，总流量 $m$ 将出现在表示边 $(s,r)$ 的流量限制的不等式中．由推论可知，最大费用 $v(m)$ 是流量 $m$ 的凹函数．

利用该费用流模型，可以通过模拟费用流或 [反悔贪心](../../basic/greedy.md#后悔解法) 的方法在 $O(n\log n)$ 的复杂度内解决该问题．

$$
f(i,j) = \max\{f(i-1,j),f(i-2,j-1)+a_i\}.
$$

将这一状态转移方程看作是函数 $f(i,\cdot)$ 的递推关系式．因为最值符号内涉及两个不同的函数，这并不能表达为卷积上确界的形式．但是，仍然可以通过归纳的方法证明函数 $f(i,\cdot)$ 是凹函数．

实际上，需要归纳地证明如下两点：

-   $f(i,j)-f(i-2,j-1)$ 关于 $j$ 递减；
-   $f(i,j)-f(i-1,j)$ 关于 $j$ 递增．

归纳起点是平凡的．假设它们对于所有 $i-1$ 及之前的自然数都成立，现在证明它对 $i$ 也成立．直接验证即可．

首先，由归纳假设，有

$$
f(i-1,j) - f(i-2,j-1) = (f(i,j)-f(i-2,j-1)) - (f(i,j)-f(i-1,j))
$$

关于 $j$ 递减．所以，有

$$
f(i,j) - f(i-2,j-1) = \max\{f(i-1,j) - f(i-2,j-1), a_i\}
$$

关于 $j$ 递减，且

$$
f(i,j) - f(i-1,j) = \max\{0,a_i-(f(i,j) - f(i-2,j-1))\}
$$

关于 $j$ 递增．这就完成了归纳．

进而，有

$$
f(i,j) - f(i,j-1) = (f(i,j)-f(i-2,j-1)) - (f(i,j-1) - f(i-1,j-1)) - (f(i-1,j-1) - f(i-2,j-1))
$$

关于 $j$ 递减．这就说明 $f(i,j)$ 是关于 $j$ 的凹函数，从而，价值函数 $v(m)=f(n,m)$ 是关于 $m$ 的凹函数．

这个证明的一个副产品是，对于任意 $i$，都存在 $p_i$ 使得

$$
f(i,j) =
\begin{cases}
f(i-1,j), & j\le p_i,\\
f(i-2,j-1) + a_i, & j> p_i.
\end{cases}
$$

这说明，可以通过平衡树直接维护序列 $f(i,\cdot)$，复杂度是 $O(n\log^2n)$ 的．但是，好处是可以处理任意种树间隔的一般情形，且一次性地获得了所有 $v(m)$ 的值．

$$
w(l,r) = \max_{i\in[l+1,r]} a_i
$$

的区间分拆问题．也就是说，每一段的收益是除去第一棵树外，其余树的收益的最大值——这就保证了间隔种树．

因为这是最大化问题，需要验证「交叉大于包含」，即对于任意 $a<b<c<d$，都成立

$$
w(a,c)+w(b,d) \ge w(a,d)+w(b,c).
$$

代入收益函数的表达式，并设

$$
A = \max_{i\in[a+1,b]} a_i,~ B = \max_{i\in[b+1,c]} a_i,~ C = \max_{i\in[c+1,d]}a_i,
$$

则要证明的不等式可以写作

$$
\max\{A,B\} + \max\{B,C\} \ge \max\{A,B,C\} + B.
$$

注意到不等号左侧的两项 $\max\{A,B\}$ 和 $\max\{B,C\}$ 中较大的那个就等于 $\max\{A,B,C\}$，而它们中较小的那个总是不小于 $B$，因此该不等式成立．

将种树问题转化为区间分拆问题后，只需要用 ST 表等方式预处理区间最值，可以单次 $O(1)$ 地计算单个区间的成本，就可以套用区间分拆问题的算法在 $O(n\log n\log L)$ 或 $O(n(n+m))$ 的时间复杂度内解决该问题．该方法同样可以处理任意种树间隔的问题．

用于刻画「边际成本递增」的一个常见性质是函数的超模性（supermodularity）．对于有限集合 $X$ 的子集族 $\mathcal PX$ 上的函数 $f:\mathcal PX\rightarrow\mathbf R$，如果它满足以下两条等价性质之一：

1.  （交叉小于包含）对于任何子集 $A,B\subseteq X$，都有 $f(A)+f(B) \le f(A\cup B) + f(A\cap B)$ 成立；
2.  （边际成本递增）对于任何子集 $A\subseteq B\subseteq X$ 以及 $x\in X\setminus B$，都有 $f(A\cup\{x\})-f(A)\le f(B\cup\{x\})-f(B)$ 成立；

就称函数 $f$ 是 **超模的**（supermodular）．但是，超模函数作为目标函数的最优化问题中，价值函数

$$
v(m) = \min_{A\subseteq X} f(A) \text{ subject to }|A|=m
$$

**未必** 是 $m$ 的凸函数．究其原因，就是从子集大小分别为 $m-1$ 和 $m+1$ 的最优解，一般来说是无法构造出子集大小为 $m$ 且满足前述价值函数大小关系的可行解的．

$$
z_i = x_i^{(m+1)} - x_i^{(m-1)},~i=1,\cdots,n.
$$

这个序列标记了两个种树方案的差异．这一序列中取值为 $0$ 的位置表示该坑位要么在两个方案中都种了一棵树，要么在两个方案中都没有种树；而取值为 $-1$ 和 $+1$ 的位置则分别表示只在方案 $x^{(m-1)}$ 或只在方案 $x^{(m+1)}$ 中，该坑位种了一棵树．因为任何方案中都不能在相邻的坑位种树，所以有如下观察：

-   连续的非零子段中，$z_i$ 的取值必然在 $\pm 1$ 之间相互交错的；
-   极大的连续非零子段左右两侧的 $0$，必然表示在两个方案中都没有种树．

因此，如果某个极大的连续非零子段中，$z_i$ 的和恰好为 $+1$，也就是说，在该段坑位中，方案 $x^{(m+1)}$ 比方案 $x^{(m-1)}$ 多种了一棵树，那么就可以在该段内交换两个方案的种树位置．这样，就得到了两个各种 $m$ 棵树的可行方案．因为没有改变两个方案中总的种树的位置和数量，只是将它们重新分配，所以总的收益不变，仍然是 $v(m-1)+v(m+1)$．但是，这两个种 $m$ 棵树的方案未必是最优的，因此，它们各自的收益不会超过 $v(m)$．这就证明了

$$
v(m-1) + v(m+1) \le 2v(m),
$$

也就是说，$v(m)$ 是关于 $m$ 的凹函数．

现在，只剩下一个问题，就是和恰好为 $+1$ 的极大连续非零子段是否存在．因为是若干个交错的 $\pm 1$ 相加，一个连续非零子段的和只能是 $0$ 或 $\pm 1$．又因为所有这些极大连续非零子段的和等于 $2$，所以，一定存在至少两个和恰好为 $+1$ 的极大连续非零子段．这就完成了证明．

应用 WQS 二分的方法移除数量限制后，问题转化为计算链上最大权独立集，只是将原本的收益 $\{a_i\}$ 替换为了 $\{a_i+k\}$．这是经典的动态规划题目．可以设 $f(i,j)$ 为第 $i$ 个坑位选择种树（$j=1$）或不种树（$j=0$）时，前 $i$ 个树坑的子问题的最大收益．由此，可以写出状态转移方程为

$$
\begin{aligned}
f(i,0) &= \max\{f(i-1,0),f(i-1,1)\},\\
f(i,1) &= f(i-1,0) + a_i + k.
\end{aligned}
$$

初始条件为 $f(0,0)=0$ 和 $f(0,1)=-\infty$，最终答案为 $\max\{f(n,0),f(n,1)\}$．单次计算复杂度为 $O(n)$，整体时间复杂度为 $O(n\log L)$，其中，$L=\max_i|a_i|$．

参考实现如下：

=== "传统方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/plant-tree-1.cpp"
    ```

=== "对偶方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/plant-tree-2.cpp"
    ```

???+ note "引理"
    设 $S$ 和 $T$ 是无向连通图 $G=(V,E)$ 的两个生成树．对于任意 $e\in S\setminus T$，都存在至少一条边 $f\in T\setminus S$，使得 $S-e+f$ 和 $T-f+e$ 都是图 $G$ 的生成树．

??? note "证明"
    设 $e=(u,v)$，且 $P$ 是树 $T$ 中连接 $u$ 和 $v$ 的唯一一条路径．因为 $P+e$ 是图 $T+e$ 中唯一的环路，所以删掉 $P$ 中的任何一条边 $f$ 都可以使得 $T-f+e$ 是一棵生成树．与此同时，图 $S-e$ 是有两个连通分量的森林，它们的顶点集分别记作 $V_1$ 和 $V_2$，所以，只要选择边 $f\in P$ 使得 $f$ 连通了 $V_1$ 和 $V_2$，就能保证 $S-e+f$ 是一棵生成树．这样的边 $f$ 总是存在的，因为 $u$ 和 $v$ 分别属于 $V_1$ 和 $V_2$，而 $P$ 连接了 $u$ 和 $v$．而且，$f\notin S$，因为图 $S-e$ 中，$V_1$ 和 $V_2$ 并不是连通的．这就完成了证明．

设 $T_{m-1}$ 和 $T_{m+1}$ 是白边数量分别为 $m-1$ 和 $m+1$ 的最小生成树．设 $e$ 是 $T_{m+1}\setminus T_{m-1}$ 的一条白边，对它应用上述引理可知，存在边 $f\in T_{m-1}\setminus T_{m+1}$，使得 $T'=T_{m+1}-e+f$ 和 $T''=T_{m-1}+e-f$ 都是生成树．因为只是交换了一对边，所以，树 $T'$ 和树 $T''$ 的边权和仍然是 $v(m-1)+v(m+1)$．进而，分两种情形讨论：

-   如果 $f$ 是一条黑边，那么，$T'$ 和 $T''$ 中的白边数量都是 $m$．它们各自的边权和都不会小于 $v(m)$．这就证明了 $2v(m)\le v(m-1)+v(m+1)$，故而 $v(m)$ 关于 $m$ 是凸的．
-   如果 $f$ 是一条白边，那么，$T'$ 和 $T''$ 的白边数量分别是 $m+1$ 和 $m-1$，所以它们的边权和分别不小于 $v(m+1)$ 和 $v(m-1)$．但是，上面已经说明，它们的边权和加在一起就等于 $v(m-1)+v(m+1)$．这说明，$T'$ 的边权和就等于 $v(m+1)$．将 $T'$ 与 $T_{m+1}$ 比较可知，$e$ 和 $f$ 的边权必然相等．这与假设矛盾，所以该情形并不成立．

这就证明了 $v(m)$ 是 $m$ 的凸函数．

建立了函数 $v(m)$ 的凸性后，就可以用 WQS 二分解决该问题．移除数量限制并将每条白边的权重都减去 $k$，并求解最小生成树问题．为此，可以应用 [Kruskal 算法](../../graph/mst.md#kruskal-算法)．利用并查集维护连通性，算法的复杂度就是 $O(E\log E+E\alpha(V))$，其中，$E$ 和 $V$ 分别为边数和顶点数，$\alpha(\cdot)$ 为反 Ackerman 函数．复杂度的主要部分 $O(E\log E)$ 是给边排序的复杂度，在本题中可以进一步优化．虽然在 WQS 二分的过程中需要多次计算最小生成树，但是每次只有白边的边权会整体加减一个数．所以，可以在预处理时给白边、黑边分别排序，然后每次计算最小生成树时，只需要将调整完权重后的白边和黑边归并到一起就可以了．这样，整体复杂度就降低到了 $O(E\log E+E\alpha(V)\log L)$，其中，$L$ 为边权的取值范围的长度．

参考实现如下：

=== "传统方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/black-white-mst-1.cpp"
    ```

=== "对偶方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/black-white-mst-2.cpp"
    ```

每个邮局服务离它最近的村庄，那么，这些村庄必然是高速公路旁连续的若干个村庄．所以，修建 $m$ 个邮局，就相当于将所有村庄划分为连续的 $m$ 段，并为每一段村庄修建一个成本最低的邮局．众所周知，邮局应当修建在村庄位置的中位数的位置．由此，可以写出区间 $[l,r]$ 的成本函数为

$$
w(l,r) = \sum_{i=l}^r|a_i-a_{\lfloor(l+r)/2\rfloor}|.
$$

它满足四边形不等式，因为它的二阶混合差分非正：

$$
\Delta_l\Delta_r w(l,r)
= \Delta_l(a_{r+1} - a_{\lfloor(l+r+1)/2\rfloor})
= a_{\lfloor(l+r+1)/2\rfloor}-a_{\lfloor(l+r+2)/2\rfloor} \le 0.
$$

这说明，可以通过二分队列结合 WQS 二分的方法在 $O(n\log n\log L)$ 的复杂度内求解该问题．

参考实现如下：

=== "传统方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/post-office-1.cpp"
    ```

=== "对偶方法"
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/post-office-2.cpp"
    ```

更一般地，可以抽象为如下问题：

给定长度为 $n$ 的三个正实数序列 $\{A_i\},\{B_i\},\{C_i\}$，而且，对所有 $i=1,\cdots,n$ 都有 $C_i\le A_i+B_i$ 成立．求最优的下标集合 $X$ 和 $Y$ 满足 $|X|=m_1$ 和 $|Y|=m_2$ 且最大化

$$
\sum_{i\in X\setminus Y}A_i + \sum_{i\in Y\setminus X}B_i + \sum_{i\in X\cap Y}C_i.
$$

$$
A_i = p_i,~ B_i = q_i,~ C_i = p_i+q_i-p_iq_i
$$

时的特殊情形．因此，只需要讨论更一般的问题的解决方案就可以了．

用 $v(m_1,m_2)$ 表示该问题的价值函数，需要证明它是关于 $(m_1,m_2)$ 的凹函数．考虑如下费用流模型：

-   从源点 $s$ 出发，分别向结点 $x$ 和 $y$ 连一条边，容量分别为 $m_1$ 和 $m_2$，费用均为 $0$；
-   对于所有 $i=1,\cdots,n$，分别从结点 $x$ 和 $y$ 向结点 $i$ 连一条边，容量均为 $1$，费用分别为 $A_i$ 和 $B_i$；
-   对于所有 $i=1,\cdots,n$，从结点 $i$ 出发向汇点 $t$ 连两条边，容量均为 $1$，费用分别为 $0$ 和 $C_i-A_i-B_i$．

问题的答案就是该费用流模型的最大费用最大流．条件 $C_i-A_i-B_i\le 0$ 保证了当流经结点 $i$ 的流量为 $1$ 时，会优先选择费用为 $0$ 的那条边流出．将这个费用流模型写成线性规划问题，那么，$m_1$ 和 $m_2$ 就会分别出现在表示边 $(s,x)$ 和边 $(s,y)$ 的流量限制的不等式中．因此，$v(m_1,m_2)$ 确实是 $(m_1,m_2)$ 的凹函数．

为了应用 WQS 二分，需要考虑移除数量限制后的最优化问题．设 $k_1$ 和 $k_2$ 分别为将一个下标放入集合 $X$ 和 $Y$ 时获得的额外奖励．没有数量限制后，关于每个下标的决策都是独立的，因此，有

$$
h(k_1,k_2) = \sum_{i=1}^n\max\{0,A_i+k_1,B_i+k_2,C_i+k_1+k_2\}.
$$

原问题的答案就由

$$
v(m_1,m_2) = \min_{k_1,k_2} h(k_1,k_2) - k_1m_1 - k_2m_2
$$

给出．总的时间复杂度为 $O(n\log^2L)$，其中，$O(\log L)$ 为对单个维度二分的次数．

抓捕神奇宝贝问题的参考实现如下：

```cpp
--8<-- "docs/dp/code/opt/wqs-binary-search/gosha-is-hunting.cpp"
```

$$
\begin{aligned}
f(a,m) &= (a\bmod (m+1))\left\lceil\dfrac{a}{m+1}\right\rceil^2 + (m+1-(a\bmod (m+1)))\left\lfloor\dfrac{a}{m+1}\right\rfloor^2 \\
&= (a\bmod (m+1))\left(\left\lfloor\dfrac{a}{m+1}\right\rfloor+1\right)^2 + (m+1-(a\bmod (m+1)))\left\lfloor\dfrac{a}{m+1}\right\rfloor^2.
\end{aligned}
$$

第二步的等号成立，是因为 $\lceil a/(m+1)\rceil \neq \lfloor a/(m+1)\rfloor + 1$ 当且仅当 $a\bmod (m+1) = 0$．

可以证明，函数 $f(a,m)$ 是关于 $m$ 的凸函数．为此，需要将它延拓到 $m\in\mathbf R_{+}$ 的情形．当 $\lfloor a/(m+1)\rfloor = q$ 时，有

$$
\begin{aligned}
f(a,m) &= (a-(m+1)q)(q+1)^2 + ((m+1)(q+1)-a)q^2 \\
&= a(2q+1) - q(q+1)(m+1).
\end{aligned}
$$

这是斜率为 $-q(q+1)$ 的直线．因此，$f(a,m)$ 是分段线性函数，且斜率随着 $m$ 的增加而增加．这就说明了 $f(a,m)$ 是凸函数，它限制在整点上当然也是凸函数[^conv-int]．

利用 $f(\cdot,\cdot)$，可以将所有线段总共切割 $m$ 次得到的最小平方和写作如下最优化问题的价值函数：

$$
v(m) = \min_{\{m_i\}}\sum_i f(a_i,m_i)\text{ subject to }\sum_i m_i=m,~m_i\in\mathbf N.
$$

这是若干个凸函数的 [卷积下确界](./slope-trick.md#卷积下确界minkowski-和)，所以也是凸函数．如果题目要求的是 $v(m)$，那么，可以使用与之前的例题一致的方法求解，时间复杂度为 $O(n\log^2L)$；但是，本题求的是满足 $v(m)\le V$ 的最小的 $m$．利用 WQS 二分计算 $v(m)$ 再对 $m$ 二分的方法是行不通的，它的复杂度达到了 $O(n\log^3L)$．就本题而言，有如下两种处理方法．

**方法一**：仍然二分斜率 $k$，但是二分的依据是对 $v(m)$ 上下界的估计．

传统的 WQS 二分的方法中，对于给定的斜率 $k$，可以计算出相应的最优的 $m$ 的取值范围．因为这些 $(m,v(m))$ 共线，所以这相当于确定了 $v(m)$ 的取值范围．因此，可以直接二分斜率 $k$．得到斜率 $k$ 之后，可以利用直线方程

$$
v(m) = h(k) + km
$$

计算出最小的 $m$．整体复杂度为 $O(n\log^2L)$．

为了确定 $v(m)$ 的取值范围，需要确定 $m$ 的取值范围．一种做法是，在计算 $h(k)$ 时记录相应的最大最优解，利用它可以计算相应的 $v(m)$ 的下界；另一种做法是，利用 $h(k)-h(k-1)$ 得到相应的 $m$ 的上界，进而得到相应的 $v(m)$ 的下界．参考实现中，采用的是第二种做法，它不依赖于问题的具体结构，无需特别处理．

**方法二**：改写最优化问题，使得对偶问题的价值函数就是本问题的解．

本问题可以直接看作是如下最优化问题：

$$
m(v) = \min_{\{m_i\}} \sum_i m_i \text{ subject to }\sum_i f(a_i,m_i) \le V.
$$

本文的分析仍然适用于这一问题．故而，可以利用它的对偶问题求解所要求的 $m(v)$：

$$
m(v) = \max_{k} \sum_i\min_{m_i}(m_i - \lambda f(a_i,m_i)) + \lambda V.
$$

整体算法复杂度仍然是 $O(n\log^2L)$ 的．

参考代码如下：

=== "方法一"
    代码仅做示意，为通过原题数据范围，需要 128 位整数，并调整二分初始区间为 $[0,10^{60}]$．
    
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/teleporters-1.cpp"
    ```

=== "方法二"
    代码仅做示意，由于浮点数精度问题无法通过原题数据范围．
    
    ```cpp
    --8<-- "docs/dp/code/opt/wqs-binary-search/teleporters-2.cpp"
    ```