题解：CF1954E Chain Reaction

Halberd_Cease · 2024-04-15 19:29:23 · 题解

容易想到，在已经将所有的 a_i 减去同一个值之后，如果要再减去同一个值（已经死亡的怪物不需要减也不能减，因此不算在内），所需步数为当前序列中连续大于 0 的段数。

考虑预处理出减去每一个值 k\in[1,\max(a_1,a_2,\dots,a_n)] 后再次操作需要的操作次数，记为 ans_k。

初始连通块（即连续大于 0 的块）个数是 1，考虑对于所有的 a_i=k，由于 a_i 在 k=a_i-1 时没有被消掉，而在当前 k 下会被消掉，因此 k=x 相对 k=x-1 时变化的地方只有 a_i=k。

枚举每一个 a_i=k，如果 a_{i-1} 和 a_{i+1} 已经全部消掉了，那么就减少一个连通块，如果两边都没有消掉就增加一个，一边有一边没有就不变。

那么我们就可以通过 k=x-1 的状态转移出 k=x 的状态，由于只有 n 个 a_i，这一步是 O(n) 的（令 n 和 \max(a_1,a_2,\dots,a_n) 同阶）。

接着对于每一个间隔 k，其答案就应该是 ans_0+ans_k+ans_{2k}+\dots+ans_{xk}，有 xk<\max(a_1,a_2,\dots,a_n)，这一步的复杂度是调和级数 O(n\ln n) 的。

submission