题意回顾

给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，构造序列 $c$：

• $c_i \in \{a_i, b_i\}$
• 恰有 $k$ 个位置 $c_i = a_i$
• 最小化 $\max(s, 0)$，其中 $s$ 是 $c$ 的最大子段和

数据范围：$n \leq 10^5$，$|a_i|, |b_i| \leq 10^9$。

---

关键观察

1. 问题转化

最大子段和 $s$ 可能为正也可能为负。
我们要最小化 $\max(s, 0)$，即：

• 如果能使 $s \leq 0$，答案就是 $0$
• 否则要最小化正的最大子段和

---

2. 初步思路

设 $d_i = b_i - a_i$。
如果我们确定哪些位置选 $a_i$（集合 $A$，$|A|=k$），哪些选 $b_i$（集合 $B$），则： $ c_i = \begin{cases} a_i & i \in A \\ a_i + d_i & i \in B \end{cases} $ 即 $c_i = a_i + [i \in B] \cdot d_i$。

---

3. 最大子段和与选择的关系

最大子段和是序列上一个连续区间的和的最大值。
我们希望这个值尽量小（非正最好）。

一个常用技巧：令 $x_i = c_i - t$，如果 $x$ 的最大子段和 $\leq 0$，则 $c$ 的最大子段和 $\leq t$。
所以可以二分答案 $t$，判断是否存在选择方案使得最大子段和 $\leq t$。

---

4. 二分答案框架

二分 $t \geq 0$，检查是否存在恰选 $k$ 个 $a_i$ 的方案，使得 $c$ 的任意子段和 $\leq t$。

等价于：$c$ 的最大子段和 $\leq t$。

---

判断可行性（给定 t）

1. 经典方法：前缀和约束

设 $p_i = \sum_{j=1}^i c_j$，则子段和 $sum[l,r] = p_r - p_{l-1}$。
最大子段和 $\leq t$ 等价于： $ \forall 0 \leq l < r \leq n,\quad p_r - p_{l-1} \leq t $ 即： $ \forall 0 \leq i < j \leq n,\quad p_j - p_i \leq t $ 这等价于： $ \max_{0 \le i \le n} p_i - \min_{0 \le i \le n} p_i \leq t $

---

2. 前缀和与选择的关系

$p_i = \sum_{j=1}^i a_j + \sum_{j=1}^i [j \in B] \cdot d_j$
设 $S_i = \sum_{j=1}^i a_j$（固定），$q_i = \sum_{j=1}^i [j \in B] \cdot d_j$（由选择决定）。

则 $p_i = S_i + q_i$。

条件变为： $ \max_{0 \le i \le n} (S_i + q_i) - \min_{0 \le i \le n} (S_i + q_i) \leq t $

---

3. 问题转化为：选择 B（大小 n-k）使 q 满足条件

$q_0 = 0$，$q_i$ 是 $d_j$（$j \in B$）的前缀和。

我们希望 $\max(S_i + q_i) - \min(S_i + q_i) \leq t$。

---

进一步转化

设 $M = \max_{0 \le i \le n} (S_i + q_i)$，$m = \min_{0 \le i \le n} (S_i + q_i)$。
条件 $M - m \leq t$ 等价于：存在常数 $C$ 使得： $m \le S_i + q_i \le m + t \quad \forall i$ 即： $C \le S_i + q_i \le C + t \quad \forall i$ 其中 $C = m$。

---

4. 调整思路

我们其实可以控制 $q_i$ 来让 $S_i + q_i$ 的波动尽量小。
$q_i$ 是某些 $d_j$ 的和，$d_j = b_j - a_j$。

---

解法

实际上，本题可以用更直接的贪心解法：

1. 初始全选 $b_i$（即 $B = \{1,\dots,n\}$，$A = \emptyset$）
2. 我们要从 $B$ 中移出 $k$ 个元素到 $A$（即原本选 $b_i$ 改成选 $a_i$）
3. 每次改变一个位置 $i$ 从 $B$ 到 $A$，$c_i$ 的变化是 $a_i - b_i = -d_i$
4. 这会使所有包含 $i$ 的子段和减少 $d_i$
5. 为了最小化最大子段和，我们应优先选择 $d_i$ 最大的位置进行切换（因为这样能最大程度降低正的最大子段和）

---

算法步骤

1. 计算 $d_i = b_i - a_i$
2. 按 $d_i$ 从大到小排序
3. 初始全选 $B$，计算此时的最大子段和 $S_{\max}$
4. 依次将 $d_i$ 最大的 $k$ 个位置改为选 $A$，重新计算最大子段和
5. 取所有情况的最小 $\max(s, 0)$

---

线性解法思路

实际上有 $O(n \log n)$ 解法：

1. 二分 $t$
2. 用贪心判断：维护前缀和 $p$，当 $p > t$ 时，必须将之前某个 $b$ 改为 $a$ 来降低前缀和，选择 $d_i$ 最大的位置改
3. 用堆维护可改的位置

---

最终算法（）

• 二分 $t$
• 初始全选 $b$，前缀和 $sum=0$，$used=0$
• 用最大堆存当前可选的 $(d_i, i)$
• 从左到右扫描：
  • $sum = sum + b_i$
  • 将 $(d_i, i)$ 加入堆
  • 如果 $sum > t$：
    • 如果堆空或 $used \ge k$，则不可行
    • 否则弹出堆顶 $(d, j)$，$sum = sum - d$，$used++$
• 最后如果 $used \le k$ 则可行

这样可在 $O(n \log n)$ 内检查一个 $t$。

---

总结

本题的核心是：

1. 二分答案 $t$
2. 贪心维护前缀和不超过 $t$，通过将 $b$ 改为 $a$ 来降低前缀和
3. 优先改 $d_i = b_i - a_i$ 大的位置
4. 时间复杂度 $O(n \log n \log W)$，其中 $W$ 是值域

通过二分答案和贪心选择，可以高效解决这个看似复杂的最优化问题。