环上邮局 / 环上决策单调性

邮局是决策单调性优化 dp 的经典应用，其属于限制段数的序列划分问题，可以通过二分队列 + wqs 二分的方式做到 $O (n \log L \log n)$ ，其中 $L$ 指的是坐标的值域，此处不多赘述。

顾名思义，环上邮局是将邮局问题搬到了环上，我们可以用其代表一类环上限制段数的划分问题，虽然我其实几乎没有见过有人出这种东西。

形式化的，环上邮局指的是如下问题：

有 $L$ 个点排成一个环，点按顺序编号为 $0 \dots L - 1$ 。有 $n$ 个人，第 $i$ 个人在点 $a_{i}$ 上。现在需要选择恰好 $k$ 个关键点，使得所有人到离自己最近的关键点的距离之和最小。

环上问题是难以直接解决的，我们考虑断环为链。但是选取某个位置断环为链也就意味着钦定划分出一个以该位置开头的区间，这并不一定是优的。一种暴力的想法是，枚举断环为链的位置，然后每次跑一遍序列邮局，这样做的复杂度是 $O (n^{2} \log L \log n)$ ，显然无法接受。

考虑我们在序列上使用的决策单调性搬到环上后有什么性质。

假设我们选取两个不同的起点断环为链，求出了两组最优划分方案 Part 1 和 Part 2，那么有结论：Part 1 划分出的每个区间内恰有一个 Part 2 的分割点。这一结论可以简称为「路径交错」。

如果知道如何证明序列上的决策单调性，上述性质是非常符合直觉的，证明也不困难。

考虑反证。若存在 Part 1 的区间内有 $2$ 个 Part 2 的分割点，则必然也存在 Part 1 的区间内没有 Part 2 的分割点（因为 Part 1 的区间个数和 Part 2 的分割点个数相等）。这也就意味着存在一组 Part 1 的区间和 Part 2 的区间 $(I_{1}, I_{2})$ 满足 $I_{2} \subset I_{1}$ ，同时也存在另一组 $(I_{1}^{'}, I_{2}^{'})$ 满足 $I_{1}^{'} \subset I_{2}^{'}$ 。

使用惯用的方法，将两组互为包含关系的区间替换成交叉形式，并且重新组合 Part 1 和 Part 2 的剩余部分得到 Part 3 和 Part 4。由于我们做了两次不劣的替换，所以 Part 3 和 Part 4 的总代价要优于 Part 1 和 Part 2（相等的情况平凡），但是由于 Part 1 和 Part 2 分别是对应起点的最优划分，它们的总代价又应当优于 Part 3 和 Part 4。这就推导出了矛盾。

上面的证明和序列形式使用了基本一致的方法，可以参考序列形式的证明辅助理解。

得到路径交错后，首先有一种简单的优化：考虑先任取起点求一组最优划分，然后找到划分出的最短的区间，其长度应当为 $O (n / k)$ 级别，接下来我们只需要从这个区间内选取起点即可，此时不必使用 wqs 二分，可以利用路径交错将划分每一段的决策点都限制在一个区间内，直接分层转移，每层用分治或二分队列维护即可。总复杂度为 $O (n \log L \log n + \frac{n^{2}}{k} \log n)$ 。

考虑如何更进一步。任取两个起点求得最优划分 Part 1 和 Part 2。Part 1 的每个区间内恰有一个 Part 2 的分割点，这些分割点将 Part 1 的区间分成了「左部」和「右部」。接下来若在左部选取一个起点求最优划分，容易发现所有分割点都应当落在左部，对右部而言也同理。这样即可进行分治，每个子问题都可以分层转移，每层用分治或二分队列维护，复杂度依赖这个子问题的候选决策点数量。分治中每层的所有子问题的候选决策点数量之和是 $O (n + c k)$ 的，其中 $c$ 为本层子问题个数，在 Part 1 最短的区间内选取起点即可使子问题数量为 $O (n / k)$ 级别。于是总复杂度为 $O (n \log L \log n + n \log^{2} n)$ 。

例题：

NFLSOJ 约会（环上邮局）
LG6455 不可视境界线 [环版本]（环上 LG5617）

一个细节是，在第一步任求一组最优划分时我们需要构造一组恰好划分 $k$ 个区间的方案，这在 wqs 二分中是有一些困难的，因为最优代价的凸包上可能有三点共线，导致我们无法恰好取到 $k$ 个区间。cmd blog 中说可以玄学扰动，这个我不是很懂。

一种确定性的构造方法是，在凸包上定位到 $k$ 所在的线段，我们可以求出左端点对应的方案 $L$ 和右端点对应的方案 $R$ ，其中 $L$ 的段数 $< k$ ， $R$ 的段数 $> k$ 。记 $L_{i}$ 表示 $L$ 划分出的第 $i$ 个区间， $R_{i}$ 同理。记 $c$ 表示 $R$ 的段数。从小到大枚举 $i$ ，找到第一个 $L_{i} \subseteq R_{i + c - k}$ ，这样的 $i$ 必然存在，考虑 $L_{i}$ 右端点第一次在 $R_{i + c - k}$ 右端点右侧的时刻即可。随后将两个区间改为交叉形式并和 $L, R$ 的剩余部分拼接即可得到一组恰好分 $k$ 段的方案，且使用证明决策单调性的方法可以证明此方案的代价取到了最优。

代码没写。

Reference

DP 的决策单调性优化总结 - command_block

本作品采用知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议进行许可。