题解：AT_abc457_f [ABC457F] Second Gap

Expert_Dream · 2026-05-11 22:10:52 · 题解

考虑从后往前枚举，当前考虑到 i，设后缀 P_i,\dots,P_n 的最大值为 a_i，次大值为 b_i。

• 当 D_i = D_{i+1} 时，a_i = a_{i+1},b_i = b_{i+1}。

• 当 D_i \ne D_{i+1} 时，此时最大值次大值会发生改变，会出现：

不难注意到，只要 D_i \ne D_{i+1} 那么必定会得出之前的最大值位置，即 i+D_i。

又因为 b_i = a_i \pm D_i ，考虑分为两种清空：

所以我们可以开两个数组存储最大值右边或者左边时的方案数。

然后从 n-2 \to 1 遍历，当 D_i \ne D_{i+1} 时：对应上述两种情况转移即可，分别是左和右。

当 D_i = D_{i+1} 时，延续之前的状态并且乘上贡献。

细节有一点多，https://atcoder.jp/contests/abc457/submissions/75667067。