2024牛客OI赛前集训营-提高组（第四场）题解

好像出的有点过于难了。。。。

另外题面有些小锅，非常抱歉。

T1

暴力是容易的，注意到一个位置一旦操作了就不会再操作了。

那么第一次操作后就相当于直接变成了链，这个链是容易做的，一个想法是从左往右操作一遍，最后检查是否有 $0$ 。这个想法是对的，因为边界只有一个数与它挨着，只能靠这个与它挨着的数变成 $0$ 。

于是有了一个 $\mathcal{O}(n^2)$ 的做法。

考虑优化，首先把链复制一份放在后面，断环成链，那么只需要检查每个长度为 $n$ 的子区间是否合法即可。

如何判断一个子区间合法呢？首先先操作一下这个子区间的头和尾，然后就变成了一条链，设链上第 $i$ 个数为 $a_i$ 。

考虑一个长度为 $n$ 的链合法的充要条件：

奇数位置上的数和=偶数位置上的数的和。
对于 $\forall 2\le i\le n$ ， $a_i \ge \sum_{j=1}^{i-1} (-1)^{i-j} a_j$ 。

第二个条件发现可以写成前缀和的形式。

于是正解做法就出来了，维护一个奇数位置的前缀和，偶数位置的前缀和，然后需要查询的是一个长度为 $n$ 的区间最小值，使用单调队列即可。

时间复杂度线性。

T2

这题不是我出的，是我同学出的，所以我就没怎么管这题。但是数据好像造水了，暴力冲过太多分了。。。非常抱歉。

先固定 $x$ , 分析取到最小值时 $(a_i,a_j)$ 的性质. 注意到 $a_i\oplus a_j$ 的大小取决于 $a_i,a_j$ 的最高不同 bit. 记 $\text{high}(x)$ 表示 $x$ 的最高 bit, 可以猜测, 当 $\textit{ans}_x$ 取到最小时, 必然有 $\text{high}(a_i\oplus a_j)$ 取到最小.

接下来, 我们来证明这个结论. 设 $w=a_i\oplus a_j$ , $h=\text{high}(w)$ 注意到

2^{h 1}-w\le|(a_i\oplus x)-(a_j\oplus x)|\le w,

因而

2^{h 1}\le \textit{ans}_x\le 2w<2^{h 2}.

令 $h\gets h 1$ , $2^{h 2}\le\textit{ans}_x'$ , 那么

\textit{ans}_x\overset{\text{constantly}}{<}\textit{ans}_x'.

利用这个结论, 设 $h_0=\min_{i\neq j}\{\text{high}(a_i\oplus a_j)\}$ , 我们只需要考虑 $\text{high}(a_i\oplus a_j)=h_0$ 的 $(a_i,a_j)$ 对答案的贡献. 另一方面, 由于此时 $\lfloor(a_i\oplus x)/2^{h_0 1}\rfloor=\lfloor(a_j\oplus x)/2^{h_0 1}\rfloor$ , 所以本质不同的 $x$ 只有 $2^{h_0 1}$ 种, 对应着最低的 $h_0 1$ 个 bit 的不同取值. 我们只需要求出这 $2^{h_0 1}$ 个答案即可, 而不必考虑所有的 $2^m$ 个值.

另一个更有趣的事实是, 直接枚举计算答案的复杂度是有保证的.

证明也很简单, $a_i$ 的高 $m-h_0-1$ 个 bit 仅有 $2^{m-h_0}$ 种取值, 而当这些 bit 固定时, 最多仅存在一对满足条件的 $(a_i,a_j)$ (否则, 由鸽巢原理, $h_0$ 的值会减小). 对于这 $\mathcal O(2^{m-h_0})$ 对 $(a_i,a_j)$ , 我们 $\mathcal O(2^{h_0 1})$ 地枚举每个 $x$ 计算答案. 最终复杂度为 $\mathcal O(2^m)$ .

此外, 对于 $h_0$ 的求解, 只需要桶排 $\{a_n\}$ 之后取 $\text{high}(a_i\oplus a_{i 1})$ 的最小值即可. 此后仅对 $\text{high}(a_i\oplus a_{i 1})=h_0$ 的 $(a_i,a_{i 1})$ 枚举 $x$ 贡献答案. 注意不要直接排序或引入 Trie 树, 我尽力卡掉了.

为什么 $n\le2^{23}$ ? 因为再大的话输入就比排序还慢了, 没有办法精准毙掉带 $\log$ 做法.

T3

居然只过了 1 个人，有点意外。

个人认为算是比较套路的 dp 题吧。

首先得搞清楚如何快速求出最大子段和，方便设计状态，设 $suf_i$ 表示以 $i$ 为结尾的最大后缀和，那么最大子段和就是所有 $suf$ 的最大值，只需统计所有 $suf_i<P$ 的方案。

$suf$ 的转移是 easy 的， $suf_i=\max(suf_{i-1} a_i,a_i)$ 。

于是就可以设计 dp 了，一个很显然但又非常关键的性质：在对 $k$ 个位置加 $1$ 后， $suf_i$ 的变化量是 $\mathcal{O}(k)$ 的。

设 $dp_{i,j,k}$ 表示选择到了 $i$ ，一共选了 $j$ 个位置，新的 $suf_{i}^{'}=suf_i k$ ，转移是很简单的。讨论第 $i 1$ 个数加不加 $1$ ，计算出新的 $suf_{i 1}^{'}$ ，然后转移即可。

优化也是简单的，观察转移可以发现本质上是一个区间平移后相加的过程，由于模数为 $2$ ，使用 bitset 优化即可。时间复杂度 $\mathcal{O}(\frac{nk^2}{\omega})$ ，不卡常数。

T4

考虑对 $T$ 集合中的串长根号分治，设阈值为 $B$ 。

如果 $|t_i|\le B$ ，考虑对其先建出一个 AC 自动机，先来看询问怎么做，如果 $r-l 1\le B$ ，直接暴力，否则可以发现只有 $[l,l B-2]$ 这一段可能会超出去，于是这一段就暴力做， $[l B-1,r]$ 就直接查一个区间和。有修改怎么办呢，考虑到修改是单点修改，相当于是在 AC 自动机上进行一个子树加，然后 $[l,l B-2]$ 需要 $\mathcal{O}(1)$ 查，于是使用 $\mathcal{O}(\sqrt{n})$ 区间加， $\mathcal{O}(1)$ 单点查就行。发现 $[l B-1,r]$ 这一段的和并不好维护，因为一个修改可能影响很多个地方的值。可以转化为以下问题：

有 $a,b$ 两个序列，下列两个操作：

对于所有满足 $l\le b_i\le r$ 的 $i$ ， $a_i\leftarrow a_i v$ 。
查询 $\sum_{i=l}^r a_i$ 。

考虑对序列分块，可以想到的是对块内的 $b$ 先排序，那么修改整块就直接在块内二分找到满足条件的区间，去维护块内的和，散块暴力重构，查询就整块直接加上维护好的整块的和，散块暴力加，需要通过二分找区间。不能暴力预处理前驱后继，否则空间就爆炸了。出题人没有刻意卡带 log 的做法。纯根号可以考虑分散层叠，但是因为分散层叠要满足每个数只能出现一次，即 $b$ 中不能有相同的数，但是实际上 $S$ 串的每个前缀可能对应的是同一个位置。但是没有关系，不如反过来，做如下问题：

对于 $l\le i\le r$ ， $a_i\leftarrow a_i v$ 。
查询 $\sum_{i=1}^n [l\le b_i\le r]a_i$ 。

可以发现上下两个问题是等价的，但是下列问题在本题中有一个特殊性，满足 $b$ 序列互不相同，这样子可以直接使用分散层叠了。

如果 $|t_i|> B$ ，这种大串只有 $\frac{\sum_{i=1}^m |t_i|}{B}$ 个，考虑直接对每个大串求出其在 $S$ 串的 endpos 集合。但是暴力求是 $\frac{|S|\sum_{i=1}^m |t_i|}{B}$ 的。考虑 bitset，先给这些大串同样建一个 AC 自动机，然后把大串挂在 fail 树上，对于 $S$ 串的每一个前缀 $i$ ，找到 fail 树上其所对应的结点 $u$ ，然后把 $i$ 先贡献到从 $u$ 到 fail 树的根这条路径上第一个有大串对应的结点。然后对这些大串挂在 fail 树上的节点的集合建一个类似于虚树的东西（只需要找到每个点有大串对应的第一个祖先就行）

，然后自底向上做一遍 bitset or。这样子做就是 $\frac{|S|\sum_{i=1}^m |t_i|}{Bw}$ 的。考虑如何查询，如果直接存 $\frac{\sum_{i=1}^m |t_i|}{B}$ 个前缀和数组，空间就爆炸了，由于强制在线所以也不能离线处理。

考虑时间与空间的平衡，先把 $a$ 序列每 $8$ 个分一块，预处理出一个 $sum_{i,j}$ 表示第 $i$ 块中， $\sum_{k=0}^7[2^k\in j]a_{8i k}$ 的值。然后再对 $a$ 序列每 $64$ 个分一块，预处理出整块的前缀和。查询就很简单了，散块暴力查，整块直接查。

这个做法的常数巨大，需要精细实现，并调块长。

令 $\omega=64$ ，复杂度为 $\mathcal{O}(m\sqrt{|S|} m\sqrt{\sum_{i=1}^m |t_i|} \frac{|S|\sqrt{\sum_{i=1}^m |t_i|}}{w} Q\sqrt{|S|}\omega^{\frac{1}{4}} 2^8 |S|)$