自动搬运

查看原文

来自洛谷，原作者为

	qbf！ Never Give Up

搬运于2025-08-24 22:38:56，当前版本为作者最后更新于2025-02-14 21:30:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先有 $mid=\dfrac{\sum_{i=1}^na_i}n$ 必定被包含。

对于每个 $i$，我们找到操作 $i$ 次后重心位置 $\le mid$ 且最大的区间，设其重心为 $L_i$，以及重心位置 $\ge mid$ 且最小的区间，设其重心为 $R_i$。

我们大胆猜测题目相当于对每个 $i$ 选择 $c_i=L_i$ 或 $c_i=R_i$，然后最小化序列 $c$ 的极差，证明如下：

假设 $L_i$ 对应的区间为 $[l,r-1]$，$R_i$ 对应的区间为 $[l+1,r]$，那么容易发现 $[l+1,r-1]$ 必定是 $L_{i+1}$ 或 $R_{i+1}$，假设它是 $L_{i+1}$：

• 假设我们选择了 $c_i=L_i$ 且 $c_{i+1}=L_{i+1}$，那么我们显然可以从 $[l,r-1]$ 走到 $[l+1,r-1]$。
• 假设我们选择了 $c_i=L_i$ 且 $c_{i+1}=R_{i+1}$，那么由于 $L_i<L_{i+1}$，故我们显然可以把 $c_{i+1}$ 调整成 $L_{i+1}$ 而不会使答案更劣。
• 假设我们选择了 $c_i=R_i$ 且 $c_{i+1}=R_{i+1}$，则我们显然可以从 $[l+1,r]$ 走到 $[l+2,r]$。
• 假设我们选择了 $c_i=R_i$ 且 $c_{i+1}=L_{i+1}$，则我们显然可以从 $[l+1,r]$ 走到 $[l+1,r-1]$。

$R_{i+1}$ 的情况是同理的。

因此我们只需将所有 $[L_i,R_i]$ 排序，然后从小到大枚举 $c$ 序列的最小值，维护 $c$ 序列的最大值即可，时间复杂度 $\mathcal O(n\log n)$。