问题分析

给定序列 $A_1, A_2, \ldots, A_n$，需要找到单调不降序列 $B_1, B_2, \ldots, B_n$ 使得 $\sum_{i=1}^n (A_i - B_i)^2$ 最小。该问题在每次修改 $A_i$ 后都需要重新求解。

核心思路

1. 几何解释与凸包

该问题等价于在二维平面上找到点 $(1, B_1), (2, B_2), \ldots, (n, B_n)$ 组成的单调链，使得该链到点 $(1, A_1), (2, A_2), \ldots, (n, A_n)$ 的垂直距离平方和最小。

关键结论：最优解 $B$ 序列是 $A$ 序列的单调回归（isotonic regression），可以通过求累积和序列 $S_i = \sum_{j=1}^i A_j$ 的下凸包来得到。

2. 凸包算法

对于前缀和序列 $S_i = \sum_{j=1}^i A_j$，其下凸包的顶点对应着最优 $B$ 序列中的常数段：

• 凸包上的每个线段对应 $B$ 序列中的一个常数段
• 线段斜率即为该段的 $B$ 值

3. 目标函数计算

最小化的目标函数可以分解为：

$$\sum (A_i - B_i)^2 = \sum A_i^2 - \sum \frac{(\Delta S)^2}{\Delta x} $$

其中 $\Delta S$ 是凸包线段的纵向变化量，$\Delta x$ 是横向变化量。

算法实现

1. 初始凸包构建

使用单调栈维护前缀和序列的下凸包：

• 从左到右扫描，维护凸包顶点
• 记录被弹出的顶点以便后续恢复

2. 修改处理

对于每个修改操作 $A_i \to k$：

• 计算目标函数的变化：$\Delta = (k^2 - A_i^2)$
• 重新计算受影响的凸包部分
• 使用二分查找确定新的凸包结构

3. 高效查询

通过预处理：

• $pref[i]$: 前 $i$ 个凸包线段对目标函数的贡献

• $suff[i]$: 后 $i$ 个凸包线段对目标函数的贡献 实现 $O(\log n)$ 的查询复杂度。

关键优化

1. 凸包维护：使用向量叉积判断凸性，$O(n)$ 构建初始凸包
2. 修改处理：只重新计算受影响的局部凸包，避免全局重构
3. 二分查找：在凸包上二分查找切点，保证 $O(\log n)$ 的修改复杂度
4. 模运算：使用预计算的逆元处理分数取模

复杂度分析

• 预处理：$O(n)$ 构建初始凸包
• 每次修改：$O(\log n)$ 重新计算局部凸包
• 总复杂度：$O(n + m\log n)$，适用于 $n, m \leq 10^5$ 的数据范围

算法总结

本题的解法基于以下几个核心洞察：

1. 几何转化：将序列优化问题转化为凸包问题，利用单调回归的理论基础
2. 分治思想：通过维护前后缀凸包，实现局部修改的高效处理
3. 数学优化：利用向量运算和二分查找优化凸包维护
4. 模数处理：针对分数结果设计特殊的模数输出方案