[SCP-S 2026] 大雨 / rain

· · 题解

好题啊，感觉质量很高。

讲讲做题的过程吧。一个显然的观察是每个 p 最多操作一次，不妨操作了 p_1<p_2<\cdots<p_k，那么其实本质上是选择给 [1,p_1],[p_1+1,p_2],\cdots,[p_{k-1}+1，p_k] 每个区间独立选择一个数异或，最后要求段内单调，段之间也单调。接下来就尝试对这个结构硬编一个 dp 出来。

首先带值域的复杂度的做法肯定是不能考虑的，得想想如何才能把值域这一维扔掉，或者说成为 dp 值。不妨先来研究一下对于区间 [l,r]，怎样的 x 才能满足段内异或 x 后单调。

即不等式 a_i\oplus x\le a_{i+1}\oplus x 成立，这个很经典啊，等价于 a_i\oplus a_{i+1} 的最高位处（设为第 h 位），x 必须要取 a_i 的第 h 位。也就是说区间 [l,r] 中满足条件的 x 需要满足某些位必须取 0/1。注意限制之间是有可能发生矛盾的。

于是考虑设计一个 dp 位 f_{i,j} 表示 [1,i] 分成 j 段其 a_i 最终能取到的最小值是多少。

考虑如何转移，枚举上一步的状态 f_{k,j-1}，那么需要选择一个 x 满足 [k+1,i] 区间中给的限制，以及 a_{k+1}\oplus x\ge f_{k,j-1} 且让 a_i\oplus x 最小，f_{i,j} 就是 a_i\oplus x 的最小值。这个 x 的选择写一个数位 dp 就行了，更直白一点就是枚举 a_{k+1}\oplus x 与 f_{k,j-1} 相等的极长前缀，下一位前面是 1 后面是 0，剩下的贪心就行了。于是就可以做到 \mathcal{O}(n^3\log V) 了。

接下来优化看上去非常困难啊，特别中间求这个 a_i\oplus x 的最小值都比较复杂。需要找一些性质来去掉段数这一维了。

不妨先去掉段之间也要单调的限制，只考虑段内的限制，设 g_i 表示把 [1,i] 分成若干个合法段的最小段数。合法段指的是该段可以选择一个 x 使得段内单调不减。注意到答案一定是 g_n-1 或者 g_n 且 g_n 一定取得到。g_n 为啥一定能取到呢，注意到每段可以选择异或的数只要是一个正整数就行，没有限制范围，那么给第 i 段多异或上 2^{114514+i} 就一定满足条件。

此外 g_n-2 是一定不可能取得到的，不然的话 g_n 就至多为 g_n-1。那什么时候取得到 g_{n}-1 呢，注意到最开始的转化是存在一段后缀不被操作的，那么就是把某个前缀 [1,pos] 分成 g_{n}-1 段，且 [pos+1,n] 的 a 单调不增，a_{pos+1}\ge a_{pos}\oplus x。

那不是还是得回到之前的 dp 了吗，一个关键的点在于只需要求 f_i 表示 [1,i] 分成 g_i 段其 a_i 最终能取到的最小值是多少。为什么呢，因为最后的 pos 是要求 g_{pos}=g_n-1，那么只能走 g_{p_1}=g_{p_2}+1(p_2<p_1) 这种转移对进行 f 的转移。

先看 g 怎么求，注意到 g 单调不减，因为所有合法的区间的子区间也是合法区间。那么 g 直接贪心求就行了，即直到限制出现矛盾再分。

再看 f，由于 g 的单调不减性，且 g_{i+1}\le g_i+1，那么可以做一个类似于分层的 dp。即找到 g_{i}=v 的极长区间 [l_v,r_v]，统一转移到 [l_{v+1},r_{v+1}]。按照之前的暴力转移可以做到 \mathcal{O}(n^2\log V)。

接下来的优化就需要上一点数据结构了，分析一下这个转移的详细过程。假设要从 i\in[l_v+1,r_v+1] 的 f_{i-1} 转移到 j\in [l_{v+1},r_{v+1}] 的 f_j。考虑维护一个满足条件的 x 的集合 S，最初 S 为满足 a_i\oplus x\ge f_{i-1} 的 x 形成的集合，接下来对于每一个 k\in[i,j-1]，(a_k,a_{k+1}) 对应的限制会让 S 中的一些数被筛掉，最后在 S 中查询 a_j\oplus x 的最小值。

注意到多个起点的 S 集合是可以共用的，也就是说从 l_v+1 开始，每次先执行加入当前起点 i，也就是在 S 中加入 a_i\oplus x\ge f_{i-1} 的 x，然后如果 i 在 [l_{v+1},r_{v+1}] 就查询，最后再执行 (a_i,a_{i+1}) 对应的限制，即去掉 S 中的某些数。

考虑使用 trie 树来维护这个 S，需要实现以下三种操作：

1.加入所有满足 a\oplus x\ge v 的 x，其中 a,v 给出。

2.只保留 trie 中第 h 位为 0/1 的数。

3.查询 trie 上 v\oplus x 的最小值。

第二种操作其实打个懒标记就行了，就是 tag_{u,d,0/1} 表示点 u 的第 d 层中往 0/1 走的子树要不要被删掉，d 这一维可以被省掉，也就是压成一个 30 位的二进制数。

第一种操作其实也是容易的，其本质上是在 trie 上覆盖若干个满二叉子树（枚举相等前缀，下一位取 1，剩下乱取这个思路就可以分析出来），显然不能真的挂一个满二叉树上去，但是同样的打个标记就行了。

但是其实还有更省空间的写法，那就是注意到第二种操作是一个全局 trie 树操作，那其实打一个全局的懒标记就行了，而删除子树等价于删除父边，于是只需要给每条边打一个时间戳，表示上一次被 pushdown 时的时间，然后只需要比较该时间与操作时间的先后就可以知道要不要删了。

但是我是建议写最开始这个容易理解的做法的，写的时候注意要垃圾回收哦。

第三种操作的话，就是跟经典的做法一样，贪心的走，每次先往最小的方向走，如果走过去发现没有数满足条件，就往另一边走。但是这样子复杂度是不是不对？其实并不是，当往最小的方向走不行的时候，说明该方向的子树已经全被删空了，直接给该儿子删了就行了。而整个过程最多新建 n\log V 个点，所以势能是对的。

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

两个写法的代码都给一下吧，觉得哪个好理解就写哪个。不过这个题好像完全没卡垃圾回收，甚至上面理论空间更大的做法空间很低，只要 26MB。

https://www.luogu.com.cn/paste/z87lh48c

https://www.luogu.com.cn/paste/hxk5q2zd