当前位置：首页 > news >正文

根号大杂烩

news 2025/9/30 20:30:37

序列分块

把一个数组简单地划分为若干块，若操作范围覆盖整块则整体操作，反之则暴力操作。由均值不等式可证，块长取 \(\sqrt{n}\) 可得到最优理论复杂度。
由于可以暴力操作且具有简单的结构，它有着比树形数据结构更为灵活的优势。同时，它还具有常数小的优势。

习题

以下是比较板的题：

【模板】线段树 1，跑的比递归式线段树快。
教主的魔法，分块+二分答案，单次查询复杂度 \(O(\sqrt{n}\log n)\)。
[Ynoi Easy Round 2017] 由乃打扑克，分块+二分答案+二分查找。

以下是比较有挑战的题：

[SNOI2022] 军队

题意简述：区间相同颜色加，区间两种颜色合并，区间求和。
注意到块内的颜色数单调不增。因此我们每个块内维护一个森林，叶子节点即为每个城市，向上代表颜色。接下来详细讲解各种操作：

整块：
- 颜色加：直接在颜色节点打 \(tag\)。
- 颜色合并：若两种颜色都存在则新建父节点，将两种颜色合并上去，否则直接改颜色。可以证明最多新建 \(2\) 倍叶子节点数量的节点数。
散块：
全部依靠暴力重构操作。
- 颜色加：重构期间判断新颜色，直接加。
- 颜色合并：重构期间记录新颜色，直接合并。

如果重构部分写 pushdown 状物复杂度是线性的，如果从底加到顶要带个 \(\log\)。不过带 \(\log\) 也能过。
可以离线后逐块处理实现线性空间。

[Ynoi2018] 五彩斑斓的世界

突刺贯穿的第二分块。
解法：分块+并查集。开一个值域大小的并查集，这样我们就可以 \(O(1)\) 修改所有块内相同的值。同时通过维护 \(siz\) 数组来快速查询某数出现的次数，且可以随并查集的合并而合并。
接下来进行复杂度分析。注意到，对于本题的修改操作，块内的最大值 \(maxn\) 单调不增。\(maxn\) 最大为 \(10^5+1\)，\(m\) 最大为 \(5\times 10^5\)，可以视为均摊 \(O(1)\)。
对于整块的修改操作，我们分两种情况讨论：
当 \(2x\ge maxn\) 时，令所有大于 \(x\) 的数减去 \(x\)，此时暴力更新 \(maxn\)。
当 \(2x< maxn\) 时，令所有小于等于 \(x\) 的数加上 \(x\)，再将块上的 \(tag\) 加 \(x\)，表示真实值为整体减 \(tag\)。
对于散块，暴力拆散原来的并查集，直接修改并更新 \(maxn\) 就好。
整块更新是均摊 \(O(1)\)，散块更新是均摊 \(O(\sqrt n)\)。
同上一道题，离线后逐块处理以实现线性空间。
以上方法无法正确处理 \(a_i=0\) 的情况。注意到，修改操作不会产生新的 \(0\)，所以直接在一开始用前缀和处理掉 \(0\) 的询问，之后就不用管了。

莫队

很神的技巧。对于一些题目，如果所求的东西难以用常规数据结构维护且可以离线，那就可以尝试莫队。我们可以来看模板题 [国家集训队] 小 Z 的袜子。
考虑维护双指针 \(l,r\) 表示当前考虑区间 \([l,r]\)，我们可以容易地从 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 转移过来。那么在移动指针的同时 \(O(1)\) 修改当前的每种颜色袜子数的平方和即可。设当前某颜色的袜子数为 \(x_i\)，答案就是

\[\frac{\sum x_i^2+\sum x_i}{(r-l+1)(r-l)} \]

现在考虑优化以减少指针移动次数。将询问离线，并将 \(n\) 分块，以询问左端点所在块编号为第一关键字，右端点为第二关键字升序排序。这样做的时间复杂度是 \(O(n\sqrt{m})\) 的。
时间复杂度证明：
序列长度为 \(n\)，询问次数为 \(m\)。
首先证明最优块长。设块长为 \(len\)，则总块数为 \(\dfrac{n}{len}\)，左指针共移动 \(O(m\cdot len)\) 次，右指针共移动 \(O(\dfrac{n^2}{len})\) 次。总共移动 \(m\cdot len+\dfrac{n^2}{len}\) 次。由均值不等式，有

\[m\cdot len+\frac{n^2}{len}\ge 2n\sqrt{m} \]

当且仅当 \(m\cdot len=\dfrac{n^2}{len}\) 时等号成立，此时 \(len=\dfrac{n}{\sqrt{m}}\)。
代入，得

\[m\cdot len+\frac{n^2}{len}=2n\sqrt{m} \]

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

以下是一些莫队技巧

奇偶排序优化

在排序右端点时，若当前左端点块编号为奇数则升序排序，反之则降序排序。

关于指针移动顺序

由于莫队经常要维护桶，在指针移动时若先执行 delete 操作，容易访问桶的负下标造成 RE，所以建议先写 add 操作再写 delete 操作。

莫队+值域分块

值域分块 \(O(1)\) 单点修改的特性很适合莫队的指针移动。
习题：

[AHOI2013] 作业
参数要吉祥

莫队+bitset

和值域分块类似，但是更好写一些。
习题：

Rmq Problem / mex
小清新人渣的本愿

带修莫队

模板题 [国家集训队] 数颜色 / 维护队列。
现在仅 \(l,r\) 不足以表达当前状态，需要加上时间维度，即 \(l,r,t\)。
现在排序以左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字。设 \(n,m,t\) 同阶，块长设为 \(n^{2/3}\)，可得到理论最优时间复杂度 \(O(n^{5/3})\)。详细证明及 \(n,m,t\) 不同阶时的具体分析较为繁琐，可以看 OI Wiki 中的证明。