题解：P5294 [HNOI2019] 序列

zzzYheng · 2025-12-13 22:07:10 · 题解

前言

这里提供一种时间复杂度为 O(n\log n(\log n+\log V)) 的做法，特别感谢 cal 老师教我分析复杂度。

题意

给定一个序列 a_{1},a_{2},\cdots,a_{n}，你需要找到一个单调不降的序列 b_{1},b_{2},\cdots,b_{n}，使得 \sum_{i=1}^{n}(a_i-b_i)^2 最小，并输出最小值。

还有额外 q 次询问，每次给定 x,y 并将 a_{x} 修改为 y，你需要在每次询问后输出最小值，询问之间相互独立。

数据范围：n,q \le 10^5,1\le a_{i},y\le 10^9。

题解

q=0

这是经典的「全序集上的保序回归问题（L_{2}）」，时间复杂度可以做到 O(n)。

Lemma 1. 如果 a_i>a_{i+1}，则最终取 b_i=b_{i+1} 一定不劣。

Proof. 考虑使用调整法，分为以下几种情况：

考虑一对 i,i+1 满足 a_{i}>a_{i+1}，不妨钦定 b_{i}=b_{i+1}，那么它们可以被合并为一个变量 x（保持序列其余位置不变），且代价函数为 f(x)=(a_{i}-x)^2+(a_{i+1}-x)^2。

进行了上述合并操作后，问题结构便产生了变化，但可以说明，在更宽泛的问题下，类似 Lemma 1 的结论仍然成立。

Lemma 2. 考虑如下问题：

给定 n 个代价函数 f_{1}(x),f_{2}(x),\cdots,f_{n}(x)，每个函数 f_{i}(x) 均是下凸函数。

你要找到一个单调不降的序列 b_{1},b_{2},\cdots,b_{n}，使得 \sum_{i=1}^{n} f(b_i) 最小。

（原问题可看作满足 f_i(x)=(a_{i}-x)^2 的问题。）

令 a_{i} 为函数 f_{i}(x) 的一个极小值的位置，则 Lemma 1 中的结论依旧成立：如果 a_i>a_{i+1}，则最终取 b_i=b_{i+1} 一定不劣。

Proof. 进行与 Lemma 1 证明中一样的调整即可。

于是我们找到一对 i,i+1 满足 a_i>a_{i+1}，可以钦定 b_{i}=b_{i+1}=x，然后将它们合并为一个变量 b'_{i}（保持序列其余位置不变），代价函数为 f'_{i}(x)=f_{i}(x)+f_{i+1}(x)。

由于下凸函数的和函数仍是下凸函数，所以我们可以不断执行上述「邻值合并」操作，直到满足 \forall 1\le i<n,a_{i}<a_{i+1}，此时直接令 b_{i}=a_{i} 就可取到代价下界。

当两个函数合并时，我们需要快速找到新的极小值位置，有如下引理。

Lemma 3. 给定 a_{1},a_{2},\cdots,a_{m}，则使得 \sum_{i=1}^{m} (a_i-x)^2 最小的 x 是 a_{1},a_{2},\cdots,a_{m} 的平均值 \dfrac{\sum_{i=1}^{m} a_i}{m}。

Proof. 利用导数易证。

于是，假设当前变量 b'_{i} 由初始变量 b_{l_i},b_{l_{i}+1},\cdots,b_{r_{i}} 合并而来，那么 a'_{i}=\dfrac{\sum_{i=l}^{r} a_{i}}{r-l+1}。

至此，我们便得到了一个时间复杂度为 O(n^2) 的算法：

• 维护当前合并成的若干连续段：[l_{1},r_{1}],[l_{2},r_{2}],\cdots,[l_{k},r_{k}]（l_{i+1}=r_{i}+1），初始 l_i=r_i=i。
• 找到一对 i,i+1 满足 a'_{i}>a'_{i+1}，将 [l_{i},r_{i}],[l_{i+1},r_{i+1}] 合并为 [l_{i},r_{i}]。
• 当合并过程结束时，取 b_{i} 为所在连续段 a_{j} 的均值即可。

对于此类区间合并问题，一个经典的优化方法是增量法：

• 枚举 i=1\sim n，使用单调栈维护前缀 [1,i] 最终合并成的若干连续段 [l_{1},r_{1}],[l_{2},r_{2}],\cdots,[l_{k},r_{k}]。

• 考虑前缀 [1,i] 时，在 [1,i-1] 中执行过的所有合并操作此时依旧可以执行。

  于是可以继承 [1,i-1] 的最终单调栈，加入额外连续段 [i,i]，并从该局面开始合并。

• 新的合并操作一定包含元素 i，否则在考虑前缀 [1,i-1] 时就会被执行。

  于是不断检查单调栈中最后两个连续段能否合并，能合并则直接合并。

• 上过程结束后便得 [1,i] 最终合并成的若干连续段。

这样，我们就得到了 q=0 时的 O(n) 算法。

一般情况

现在，我们需要快速求解修改序列中一个元素后的答案。

依旧考虑上述连续段合并算法。假设修改操作为 a_x\gets y，那么前缀 [1,x) 和后缀 (x,n] 是不改变的，因此原序列中位于 [1,x) 和 (x,n] 内的所有合并操作现在仍可执行。

于是我们可以预处理出所有前缀和后缀的连续段合并最终结果。假设 [1,x) 的合并结果是 [l_1,r_{1}],[l_{2},r_{2}],\cdots,[l_{k_1},r_{k_1}]，(x,n] 的合并结果是 [l_{k_{1}+2},r_{k_1+2}],[l_{k_{1}+3},r_{k_1+3}],\cdots[l_{k_{1}+k_2+1},r_{k_1+k_2+1}]，那么我们可以直接从局面 [l_1,r_{1}],\cdots,[l_{k_1},r_{k_1}],[x,x],[l_{k_{1}+2},r_{k_1+2}],\cdots[l_{k_{1}+k_2+1},r_{k_1+k_2+1}] 开始合并（不妨令 l_{k_1+1}=r_{k_1+1}=x）。且此后所有的合并操作一定均包含元素 x，否则在之前就会被执行。

考虑维护包含 x 的连续段 [l_{p},r_{q}]，暴力算法便是将 [l_{p},r_{q}] 不断向两侧尝试合并。

考虑优化该过程，注意到任意时刻 [l_p,r_q] 向某一侧连续合并的最多多次数是可以快速求解的：

• 假设 [l_{p},r_{q}] 向左侧连续合并后会得到 [l_{p_0},r_{q}]。那么在 p_{0} 处具有二段性：
  • 若 p_{1}\le p_{0}，则连续段 [l_{p_1},r_{q}] 一定与左侧连续段满足均值单调性。
  • 若 p_{2}>p_0，则连续段 [l_{p_2},r_{q}] 一定不与左侧连续段满足均值单调性。
• 于是可以二分得到 p_0 的值。向右侧的连续合并可以同理计算。

基于此，我们可以交替地向两侧连续合并，每次都使用上述方法以 O(\log n) 的复杂度快速计算出连续合并至的位置。

可以证明，连续合并方向切换的次数不会超过 O(\log n+\log V)，因此时间复杂度为 O(n+q\log n(\log n+\log V))。

时间复杂度分析

令 v(l,r)=\dfrac{\sum_{i=l}^{r} a_i}{r-l+1}，设 d=\max(v(l_{p-1},r_{p-1})-v(l_{p},r_{q}),v(l_{p},r_{q})-v(l_{q+1},r_{q+1})),w=r_{q}-l_{p}+1。

忽略第一次连续合并，我们观察 d 的变化过程，其具有如下简单性质：

• 具体地，向左侧合并时有 $v(l_{p},r_{q})<v(l_{q+1},r_{q+1})$，向右侧合并时有 $v(l_{p-1},r_{p-1})<v(l_{p},r_{q})$。

• 当 d\le 0 时，过程结束。

不妨假设当前向左侧合并，我们尝试分析 d 和 w 的变化：

• 假设当前由 [l_p,r_{q}] 合并至 [l_{p'},r_{q}]，那么会新增 l_{p}-l_{p'} 个值不超过 v(l_{p-1},r_{p-1}) 的元素。（将连续段中元素均看成平均值）
• 若 l_{p}-l_{p'}\ge w，则 w 会翻倍。
• 若 l_{p}-l_{p'}<w，则新平均值 v(l_{p'},r_{q})\le \dfrac{w\cdot v(l_p,r_{q})+(l_{p}-l_{p'})v(l_{p-1},r_{p-1})}{w+(l_{p}-l_{p'})}\le \dfrac{v(l_{p},r_{q})+v(l_{p-1},r_{p-1})}{2}，而 v(l_{q+1},r_{q+1})> v(l_{p},r_{q})，因此新的 d'=v(l_{p'},r_{q})-v(l_{q+1},r_{q+1})\le \dfrac{v(l_{p},r_{q})+v(l_{p-1},r_{p-1})}{2}-v(l_{p},r_{q})=\dfrac{d'}{2}。

向右侧连续合并时同理。

因此每次连续合并后，要么 w 翻倍，要么 d 减半。而 w 的值域为 [1,n]，d 的值域为 [\frac{1}{n^2},V]，因此最多交替连续合并 O(\log n+\log V) 次。