题解 P4135 作诗？？？

· · 个人记录

萌新第一次写题解qwq

我很慌张，因为现在我没有看到资料表明这题容易做到 o(n^{1.5})。但做到这样似乎是显然的。如果找到请告知，谢谢！

upd：大概是对的qwq

首先用区间颜色数减去出现奇数次的数。

根号分治。对于出现次数 \le n/B 的数，可以考虑扫描线，即每次进行 O(\dfrac n B) 次区间加，然后进行 O(n) 次区间查询。考虑到在线，所以使用可持久化的 O(1)-O(n^{eps}) 的分块，就可以把这部分做到 O(\dfrac {n^2} B)。

对于出现次数 >n/B 的数， 分块。将序列分为 B 块。考虑一段整块的计算，显然求出每个前缀块的 bitset b，这里有 B 种不同的数所以 bitset 规模是 O(B)。块 x 到块 y(x<y) 的答案就是 popcount(b_{x-1} \oplus b_y)。求出每对块的答案，时间复杂度 O(\dfrac {B^3} w)。

计算这部分散块的贡献，就是求区间中某数出现次数。这个可以直接维护每个块的端点在每种数中的位置。规模为 O(B^2+n)。

综上，若认为 q=\Theta(n)，那么时间复杂度为 O(\dfrac {n^2} B+\dfrac {B^3} w)。取 B=\sqrt{n}/w^{1/4}，时间复杂度 O(n\sqrt n/w^{1/4})。

利用快速 01 矩阵乘法，可以做到更优秀的时间复杂度。

注意到这里是 xor 而标准的 01 矩阵乘法是 and 的形式。其实容易证明他们等价。

可以证明区间出现奇数次的数的数量不弱于 \sqrt n\times \sqrt n 的 01 矩阵乘法qwq

首先 xor 矩阵乘法等价 and 矩阵乘法，证明：

其实我们求出的 A 和 B 的 xor 矩阵乘法 C=p-(t-A)\times (t-B)-A\times B。p 是全是 n 的矩阵，t 是全是 1 的矩阵。

那么有 C=p-t\times t+t\times B+A\times t-A\times B\times 2。

显然和 t 相关的矩阵乘法容易快速计算，所以可以通过 C 解出 A\times B。

用 and 矩阵乘法算 xor 矩阵乘法直接代入即可。

xor 矩阵乘法等价于，给 n 个集合 s_{1\dots n}，求两两不交并的大小。

构造序列 s_1\ s_1\ s_2\ s_2 \dots s_n \ s_n，对于求 s_x,s_y(x<y)，查询右边的 s_x 到左边的 s_y 区间出现奇数次的数的数量即可。