收集了最近做的一些块状数据结构题，涉及分块，莫队，块状链表等，难度大多不是很高，~~老少皆宜~~。 QAQ

P4168 [Violet]蒲公英

大意：静态在线区间众数

先离散化，预处理出 \(cnt_{i,j}\)　和 \(mode_{i,j}\)，分别表示前 \(i\) 块中数值 \(j\) 出现的次数和第 \(i\) 到第 \(j\) 块的众数。可以 \(\mathcal{O}(n\sqrt{n})\) 实现（\(mode_{i,j+1}\) 可由 \(mode_{i,j}\) 在 \(\mathcal{O}(\sqrt{n})\) 的时间内推出）。

对于每次查询，答案要么在散块，要么在整块。只需扫描散块的所有数，判断其是否可以更新答案即可。

时间复杂度 \(\mathcal{O}((n+m)\sqrt{n})\)。

参考代码链接

P4135 作诗

题目链接

大意：静态在线区间出现正偶数次的数值的个数

先分享一个我的奇怪做法，

显然，\(出现正偶数次的数值的个数 = 区间数值个数 - 出现奇数次数值的个数\)，

区间数值个数主席树很好做，我们考虑如何处理出现奇数次数值的个数，

用 \(cnt_i\) 表示 \(i\) 出现的次数，如果暴力计算，每逢一个数 \(v\)，就让 \(cnt_v\) 加一，那么只要统计 \(cnt\) 中的奇数的值的数量即可，

我们让 \(cnt_i\) 的值模 2，可以发现，加一就相当于 \(cnt_v=cnt_v ~\texttt{xor}~1\)。

于是思路就很明显了，对序列分块，设块长为 \(T\)，预处理 \(\mathcal{O}(\dfrac{n}{T})\) 个 \(\texttt{bitset}\) 对于第 \(i\) 个 \(\texttt{bitset}~cnt_i\)，存储第 1 到第 \(i\) 块末尾这些数按上面的方式做出的结果（即 \(cnt_{i,j}\) 表示前 \(i\) 块中数值 \(j\) 出现次数的奇偶性），这个东西是前缀可减的（\(cnt_{p,j}~\texttt{xor}~cnt_{q,j}\) 表示第 \(p\) 到第 \(q\) 块数值 \(j\) 出现次数的奇偶性），加上散块暴力，单次询问复杂度为 \(\mathcal{O}(\dfrac{n}{w}+T+\log n)\) (假设 \(n\) 与值域同阶, \(\log\) 为主席树复杂度)。

对于预处理，每个块分别预处理，然后做一个前缀 \(\texttt{bitset}\) 异或即可，预处理时间复杂度 \(\mathcal{O}(\dfrac{n^2}{Tw})\)。

总的时间复杂度就是 \(\mathcal{O}(\dfrac{n^2}{Tw}+m(\dfrac{n}{w}+T+\log n))\)，由均值不等式，取 \(T=\dfrac{n}{\sqrt{mw}}\) 即可取到理论最优复杂度。（实际调块长很玄学QAQ）

可通过本题，但是我的写法跑的不快awa

参考代码链接

下面分享一下正宗 \(\mathcal{O}(n\sqrt{n})\) 做法

预处理出数组 \(s_{i,j}\)，表示第 \(i\) 到第 \(j\) 块这些整块的答案，可以 \(\mathcal{O}(n\sqrt{n})\) 实现。

对于每组询问，扫描散块的数，计算对答案的影响即可，实现的时候有些细节要注意。

参考代码链接

P4396 [AHOI2013]作业

题目链接

题目大意：静态询问区间值在 [a,b] 内的数的个数和数值的个数

考虑莫队，指针总共移动 \(\mathcal{O}(n\sqrt{m})\) 次，查询答案 \(\mathcal{O}(m)\) 次，因此我们需要一个 \(\mathcal{O}(1)\) 修改，\(\mathcal{O}(\sqrt{n})\) 查询的数据结构。我们只需要对值域分块即可，维护每个块内数值的个数和数的个数，查询的时候散块暴力查询，整块直接加上标记就可以了。

时间复杂度 \(\mathcal{O}(n\sqrt{m}+m\sqrt{n})\)。调一下块长跑得飞快。

参考代码链接