![[20250206.pdf]]

模拟赛

T1

感觉跟之前查询最大值那题很像

$$f(x)=(x \oplus a)-b$$

$$f(x_{i}) \times f(x_{i+1}) \le 0$$

此时答案由两种可能构成：

$$\begin{cases}(x \oplus a)-b=0 \
(f(x_i)) \not = (f_{x_{i+1}})\
\end{cases}$$
上面那个显然是可以一棵trie树维护的

对于下面那个，我们先考虑判断是否存在合法答案，即是否所有数都是同号

如何判断一个区间是否有正负数呢？其实也就是判断区间内 $\oplus a$ 的最大值和最小值即可

这时候就可以上我们那四个模板了，看看哪个最适合这道题

因为单点修改，所以主席树就不合适了

我们考虑一个弱化版的问题：从左往右数第一个大于 $b$ 的数在哪里

显然找出第一个大于与第一个小于后，必定有一个满足答案

所以可以考虑在trie树上二分

对于找第一个大于的问题，我们可以考虑在trie树上每个节点维护一个 $Min$ 表示最小下标

然后在搜索过程中若有 $\oplus a$ 后与 $b$ 异号的节点，直接输出即可

找小于同理，若有任意一个没能找到则返回

然后就做完了

T2

考虑进行放缩，将定义更改为 “若有长度为 $k(r+b)$” 的区间，且区间内 $R,B$ 数量分别为 $kr,kb$ ，则可以消除

发现这样定义后就不再会产生嵌套，且一定与原问题等价

欸这能证明吗？好像不太会证

考虑设数量较小那个为 $X$ ，较大为 $Y$ ，数量分别为 $x,y$

那么最平均的情况下， 每 $x$ 个 $X$ 都能够分到 $y$ 个 $Y$

T3

考虑这么一件事

首先最后面建出来的图一定是一棵树，其次由单调栈相关知识可得能够
建的天桥的数量一定是 $O(n)$ 级别的

所以其实每条桥已经确定，问题在于如何去确定他们在对应区间上的取值

发现每条桥之间相互独立，所以我们可以考虑拆贡献

哦并非独立

不妨设每条路径的贡献为在LCA处匹配，考虑设 $f_{x,i}$ 表示在点 $x$ 处建造高度为 $i$ 的天桥的最小贡献，发现是一个凹函数

也是成功的换题了

欸可以这么玩

你可以先将 $a_{i} \oplus a_{i+1}$ ，然后再让 $a_{i-1} \oplus a_{i}$ ，最后再 $a_{i} \oplus a_{i+1}$，也就是说后边的数字实际上可以不改变，进而也就说明了一个位置处能够变化的数其实就是他的后缀线性基异或上他本身能够表示出来的数
因为线性基只会添加 $log$ 次，所以考虑将他们进行分段

考虑一个朴素的暴力，在正常 dp 的过程中暴力的线性基去求 “是否能够正好比某数大”

考虑暴力的去匹配每一位，得出一个最接近于该数的其大或比其小的数

若比其更大，则可以暴力跳令其变得更小

若比其更小，则找到第一个能匹配上的位置再暴力跳

时间复杂度 ： $O(n^2log)$ ，理论能过50

下午讲评

.l

T2 upd

考虑跟之前那样将线性基相同的一段分离出来

由于这段的线性基相同，也就意味着 这段的每个值都 其实都能够被线性基表示出来，因此 $a_i$

于是乎这段的值一定是连续一段上升的最优，所以其实只要对 $log_V$ 个主元进行转移即可

问题就变成了我们如何用 $log$ 的时间求出前 $k$ 大的，似乎也是好做的

先找小于该数的第一个数，找到排名，将排名+len再求即可

所以是 $O(nlognlogV)$ 的

![[杂题选讲.pdf]]