P17725 [SCP-S 2026] 大雨 / rain

_Yonder_ · 2026-10-18 00:04:02 · 题解

最后 10min 才会。

发现问题等于找一个序列 b 使得 a_{i-1}⊕b_{i-1}\le a_i⊕b_i 求 \min(\sum[b_{i-1}=b_i])。

也就是说问题等价于划分最小段数，使得每一段异或一个值后合法，于是我们设 1\sim n 最小可以划分为 g_n 段，那么答案为 g_n 或 g_n-1。

假设 a_{i-1},a_i 最高不同位为 k，则它们所在段一定满足异或的 x 的第 k 位为 a_{i-1} 的第 k 位，于是 g 就可以 O(n) 求了。

我们考虑如何求出是否可以取到 g_n-1，相当于判断是否存在一个位置满足 g_{i-1}=g_n-1\land a_{i-1}⊕b_{i-1}\le a_i\le a_{i+1}\le\dots\le a_n，于是我们要对 i 维护 d_i 表示在满足 1\sim i 答案为 g_i 的情况下，\min(a_i⊕b_i) 是多少。

我们考虑对 g 分层，扫 i 的时候相当于要么进入下一层，要么不动。需要维护两棵字典树支持：保留与 a_{i-1} 第 k 位相同的 x，加入 x⊕a_i\ge d_{i-1} 的 x，查询 \min(x⊕a_i)。都是基本操作。

时间复杂度 O(n\log V)。