题解：AT_npcapc_2024_d Two Box

drmr · 2026-10-21 20:59:41 · 题解

考虑怎么解决 Q = 1 的问题。

按照编号从大到小的顺序，依次确定每个球的行为。对于球 k，他仅能出现在 A_i \ge k 的位置。

取出所有的 A_i \ge k 的位置，它们构成了若干极长连续段。则对于每一段 [l, r], r \ne n 来说，球必须在 [l, r + \bold{1}] 的操作内操作偶数次。当然，若 r = n 则无限制。

对于所有的 k 生成的连续段集合拥有类似树的性质。其中当 k = 1 时仅存在一个连续段 [1, n]，作为树根。对于 k + 1 生成的连续段，向 k 生成的唯一包含它的连续段连边。

dp。对于第 k 层的其中一个连续段，考虑记 f_0, f_1, \cdots, f_d。f_x 表示：选完了 \ge k 的球所占有的操作后，在该连续段中仍剩 f_x 次操作。同样的，g 表示选完了 \ge k 的球所占有的操作后，在当前连续段中仍剩 g_x 次操作。