题解：P17725 [SCP-S 2026] 大雨 / rain

Alastair · 2026-10-18 20:46:48 · 题解

赛时到最后都不会，赛后发现有一步走错了，后面就都有问题了。

首先对原问题进行分析，一定是分成几段，每一段的同时异或一个数。

当 a_n = 0 时，意味着一定会将 n 异或一次。

那么可以发现一个方案合法只要一个段内的所有数可以异或同一个数做到单调不降即可。

因为可以给第一个段异或 2^{32}，第二个段 2^{33}，以此类推。

考虑怎么判断一个段是否合法。赛时想法是递归的判断，但（赛后）才发现这样是复杂的，因为可以把关系拆到相邻两个数上，那么对于 a_i 和 a_{i + 1} 而言，从高位到低位，第一个不同的位置，最终这一段异或的数在这一位上一定是和 a_i 一样的。

那么这样就可以 O(n) 的做出特殊性质了，记 g_n 表示 \{ a_1, a_2, \dots, a_n \} 在上述做法的最优分段个数，这个也可以 O(n) 计算，记 l_x 和 r_x 表示第 x 个划分的区间是 [l_x, r_x]。

考虑设计状态：f_{i, j} 表示考虑 [1, i] 分成了 j 段时 a_i \oplus x 的最小值。

那么直接转移就是 O(n^3 \log V)，假设 f_{k + 1, j - 1} 转移到 f_{i, j}，那么可以通过 [k + 1, i] 确定那些位是固定的，然后接下来按位做一个贪心。

考虑到现在假设确定了一段区间异或同一个数字，那么他是不能包含 g_n 的最优划分方案中的区间的。故答案只能是 g_n 或 g_n - 1，而同样地，在最优方案下，i 只会被 [l_{x - 1} + 1, r_{x - 1}] 转移到，记 i 被划分到了第 x 个区间在 a_n = 0 时。

而当答案是 g_n - 1 时一定一段后缀被有被异或，故需要考虑的状态 j 一定为 g_j。

而现在做这个问题就是 O(n^2 \log V) 了。

当 i 在 [l_x, r_x] 时它的上一个端点在 [l_{x - 1} + 1, r_{x - 1}]，考虑统一维护，那么现在要求找到所有 a \oplus x \ge v 的 x 加入集合 S，并且限制 S 中的数字的某一位为 0 / 1，找到集合 S 内数字 x 使得 a \oplus x 最小。

对一第一种操作在 trie 树上在对应的子树的根打个标记即可，表示以这个点为根的子树中都能往下走，对于第二种操作，可以打个懒标记，记 lazy_{x, d, 0 / 1} 表示以 x 为根的子树中是否要求第 d 位为 0 / 1，可以对 d 压位，变成记 lazy_{x, 0 / 1} 表示以 x 为根的子树中要求第 x 位为 0 / 1 的那些位置构成的集合，对于第三种操作就是 trie 树上的贪心了能走就走。

总时间复杂度：O(n \log n)。（单次查询内）