题解：P10920 宇宙射线
WorldMachine
·
·
题解
🐛🛴🚀，来一个 \mathcal O\left(n\sqrt{\dfrac{n\log n}{w}}\right) 做法！不过跑的飞慢。
首先，对于固定半径 p，定义冲突数组：
d_p(i)=[(s_i=0\land s_{i+p}=1)\vee(s_i=1\land s_{i+p}=0)]
考虑把原串按照块长 $B$ 分块，对于起点为 $l$ 的整块，定义：
$$
A_0(k)=[s_{l+k}=0];\qquad A_1(k)=[s_{l+k}=1]
$$
同时对于原串，定义：
$$
S_0(k)=[s_k=0];\qquad S_1(k)=[s_k=1]
$$
那么该块与起点为 $i$ 的子串的冲突个数为：
$$
C_l(i)=\sum_{j=0}^{B-1}(A_0(j)T_1(i+j)+A_1(j)T_0(i+j))
$$
这是差卷积，把 $A_0,A_1$ 翻过来做正常卷积即可。
对于半径 $p$，该块合法当且仅当 $C_l(l+p)=0$。
这部分预处理的时间复杂度是 $\mathcal O\left(\dfrac{n^2\log n}{B}\right)$ 的。
再考虑对 $p$ 根号分治，对于 $p<4B$，直接遍历一遍判断即可，复杂度 $\mathcal O(nB)$。
对于 $p\ge4B$，找出预处理好的好块连续段，如果长度已经够了就直接合法。
否则假设有连续 $k$ 个好块，那么要有 $kB+2(B-1)\ge p$ 才可能成为一组解。
因为 $p\ge4B$，有 $kB>\dfrac p2$。由于极长段互不相交，这样的段只有 $\mathcal O\left(\dfrac np\right)$ 个。
每个极长段暴力枚举散块，这部分的复杂度是 $\mathcal O\left(\displaystyle\sum_{p=4B}^{n/2}\dfrac{nB}{p}\right)=\mathcal O(nB\log n)$。
取 $B=\mathcal O(\sqrt n)$，此时有时间复杂度 $\mathcal O(n\sqrt n\log n)$。
---
考虑进一步优化，这里用到了和 [P5063](https://www.luogu.com.cn/problem/P5063) 类似的技巧。
对 $p$ 倍增分段，设 $P=2^k$，考虑 $[P,2P)$ 内的 $p$，每段独立选取块长 $B$（保证 $4B\le P$）。
对于起点为 $l$ 的块，只需知道它与 $[l+P,l+2P)$ 内的子串的匹配情况。
因此只用把这段子串截出来卷即可，复杂度是 $\mathcal O\left(\dfrac{nP\log P}{B}\right)$ 的。
其它部分保持不变，暴力枚举散块的复杂度是 $\mathcal O\left(\displaystyle\sum_{p=P}^{2P}\dfrac{nB}{p}\right)=\mathcal O(nB)$。
单层复杂度 $\mathcal O\left(\dfrac{nP\log P}{B}+nB\right)$，取 $B=\mathcal O(\sqrt{P\log P})$ 有复杂度 $\mathcal O(n\sqrt{P\log P})$。
对每段求和，时间复杂度为 $\mathcal O\left(n\displaystyle\sum_{k=0}^{\lfloor\log_2 n\rfloor}\sqrt{k2^k}\right)=\mathcal O(n\sqrt{n\log n})$。
---
考虑优化散块的匹配，这个用 `ull` 压一下是好做的。
单层的复杂度变为 $\mathcal O\left(\dfrac{nP\log P}{B}+\dfrac{nB}{w}\right)$。
取 $B=\mathcal O(\sqrt{wP\log P})$，此时有复杂度 $\mathcal O\left(n\sqrt{\dfrac{n\log n}{w}}\right)=\mathcal O(n\sqrt n)$。
代码拐了只哈基米来写，比 $\mathcal O\left(\dfrac{n^2}{w}\right)$ 慢了一倍。
