1954E - 连锁反应 详细题解（官方标程版）

题目回顾（简洁版）

有 $n$ 个怪物排成一排，第 $i$ 个怪物血量为 $a_i$。 对于每个 $k \in [1, \max(a_i)]$：

• 每次选择一个怪物攻击，造成 $k$ 点伤害，并向左右连续穿透活着的怪物。
• 碰到死亡怪物或边界时停止。 求杀死所有怪物的最小秒数。

---

一、单个 $k$ 的答案公式（标程核心结论）

1.1 $k=1$ 时

总次数为：

$$ans(1) = a_1 + \sum_{i=2}^{n} \max(0,\ a_i - a_{i-1}) $$

1.2 任意 $k$ 时

将血量替换为向上取整：

$$b_i = \left\lceil \frac{a_i}{k} \right\rceil$$

答案公式不变：

$$ans(k) = b_1 + \sum_{i=2}^{n} \max(0,\ b_i - b_{i-1}) $$

---

二、公式化简（关键：贡献系数 $c_i$）

标程证明：上式可以改写为独立贡献和：

$$ans(k) = \sum_{i=1}^{n} c_i \cdot \left\lceil \frac{a_i}{k} \right\rceil $$

其中系数 $c_i$ 定义：

$$c_i = \begin{cases} 1 & i=1 \ \text{且}\ a_i \ge a_{i-1} \\ 1 & i>1 \ \text{且}\ a_i \ge a_{i-1} \\ 0 & i>1 \ \text{且}\ a_i < a_{i-1} \end{cases} \quad - \begin{cases} 1 & i < n \ \text{且}\ a_i < a_{i+1} \\ 0 & \text{else} \end{cases} $$

最终极简形式：

$$c_i = \begin{cases} +1 & a_i > a_{i-1} \\ -1 & a_i < a_{i+1} \\ 0 & \text{其他} \end{cases} $$

（边界 $a_0=0,\ a_{n+1}=+\infty$）

---

三、最终答案表达式（标程最终式）

$$\boldsymbol{ans(k) = \sum_{i=1}^{n} c_i \cdot \left\lceil \frac{a_i}{k} \right\rceil} $$

这就是每个 $k$ 对应的答案。

---

四、复杂度优化（标程两种解法）

方法 1：整除分块（根号优化）$O(n\sqrt{A})$

$\left\lceil \frac{a_i}{k} \right\rceil$ 只有 $O(\sqrt{A})$ 种取值。 对每个 $a_i$，枚举所有取值 $v$，找到对应 $k$ 区间 $[L,R]$，用差分批量贡献：

$$diff[L] += c_i \cdot v,\quad diff[R+1] -= c_i \cdot v $$

最后求前缀和得到所有 $ans(k)$。

方法 2：区间枚举优化 $O(A\log A)$

对每个 $k$：

$$\left\lceil \frac{a_i}{k} \right\rceil = v \iff a_i \in [(v-1)k+1,\ vk] $$

按段统计 $c_i$ 之和，总段数 $O(A\log A)$，可线性算出所有答案。

---

五、标程算法流程

1. 预处理系数 $c_i$
2. 设 $A = \max(a_i)$
3. 建立差分数组 $diff[1..A]$
4. 对每个 $i$：
   • 枚举 $\left\lceil \frac{a_i}{k} \right\rceil$ 的所有分段 $[L,R],v$
   • $diff[L] += c_i \cdot v$
   • $diff[R+1] -= c_i \cdot v$
5. 对 $diff$ 求前缀和，得到 $ans[1..A]$
6. 输出 $ans[1],ans[2],...,ans[A]$

---

六、复杂度

• $A = \max(a_i) \le 10^5$
• 时间：$O(n\sqrt{A})$ 或 $O(A\log A)$
• 空间：$O(A + n)$
• 可轻松通过 $n \le 10^5$ 限制

---

七、标程最终结论（最重要 3 条）

1. 对任意 $k$，答案为$$ans(k)=\sum_{i=1}^n c_i \cdot \left\lceil \frac{a_i}{k} \right\rceil $$
2. $c_i$ 只由 $a_i$ 与左右相邻值的大小关系决定。
3. 使用整除分块+差分可在 $O(n\sqrt{A})$ 内求出所有 $k$ 的答案。