根号大杂烩

序列分块

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

习题：

以下是比较板的题：

• 【模板】线段树 1

• 教主的魔法，分块+二分答案。

• [Ynoi Easy Round 2017] 由乃打扑克，分块+二分答案+二分查找。

• [HNOI2010] 弹飞绵羊

• [Violet] 蒲公英

以下是比较有挑战的题：

[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$ 分块，以询问左端点所在块编号为第一关键字，右端点为第二关键字升序排序。块长设置为 $\dfrac{n}{\sqrt m}$，这样做的时间复杂度是 $O(n\sqrt{m})$ 的。

时间复杂度证明

序列长度为 $n$，询问次数为 $m$。
首先证明最优块长。设块长为 $len$，则总块数为 $\dfrac{n}{len}$，左指针共移动 $O(m\cdot len)$ 次，右指针共移动 $O\left(\dfrac{n^2}{len}\right)$ 次。总共移动 $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})$，在块长 $len=\cfrac{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 中的证明。

• 树上莫队
  把树拍到括号序上，记录 $vis$ 数组表示当前选/不选节点，每次访问到节点时反转 $vis$ 即可。

根号分治

[NOI Online #1 入门组] 跑步
对和为 $n$ 的可重集计数。
考虑两种方法：

• 设 $f_{i,j}$ 表示集合中的数不超过 $i$ 且和为 $j$ 的方案数，使用类似完全背包的转移：

  $$f_{i,j}=f_{i-1,j}+f_{i,j-i}$$

  $f_{n,n}$ 即为答案，时间复杂度 $O(n^2)$。
• 设 $g_{i,j}$ 表示集合中有 $i$ 个数且和为 $j$ 的方案数，我们每次可以给集合中新加入一个 $1$ 或者令集合中的数整体加 $1$：

  $$g_{i,j}=g_{i-1,j-1}+g_{i,j-i}$$

  $\sum_{i=0}^n g_{i,n}$ 即为答案，时间复杂度 $O(n^2)$。

考虑将这两个做法融合一下：我们令小于 $B$ 的数使用第一个方法，时间复杂度 $O(Bn)$，大于等于 $B$ 的数使用第二个方法，时间复杂度 $O(Bn)$（把加入 $1$ 和整体加 $1$ 中的 $1$ 改为 $B$），之后可以枚举使用第一个方法选出和为 $i$ 的方案数，求用第二个方法选出和为 $n-i$ 的方案数相乘后累加即可，取 $B=\sqrt n$ 可以做到 $O(n\sqrt n)$ 的复杂度。

---

无向图三元环计数
将无向图定向：若 $u,v$ 度数不同，则方向为度数小的向度数大的连边，否则编号小的向编号大的连边。容易证明这样定向后的图是有向无环图。同时也容易得出原图上的三元环 $(u,v,w)$ 在新图上一定是一个形如 $(u\to v),(v\to w),(u\to w)$ 的子图。则我们直接暴力遍历所有 $u$，先将 $u$ 可达的点打上标记，遍历 $v,w$，检查 $w$ 是否被打上标记即可。
下面证明这个算法的复杂度是 $O(m\sqrt m)$ 的：
设 $E$ 为原图，$E'$ 为新图，$\text{outdeg}(u)$ 表示 $u$ 在 $E'$ 上的出度，$\text{deg}(u)$ 表示 $u$ 在 $E$ 上的度数。
将所有点分配到以下两个集合：

• $S_1=\{u|\text{deg}(u)\le \sqrt m\}$；
• $S_2=\{u|\text{deg}(u)>\sqrt m\}$。

则该算法时间复杂度为：

$$O\left(\sum_{(u\to v)\in E'}\text{outdeg}(v)\right)$$

下证所有 $u$ 的 $\text{outdeg}(u)$ 都是 $O(\sqrt m)$ 的：

• $u\in S_1$：
  显然 $\text{outdeg}(u)\le \text{deg}(u)\le \sqrt m$。
• $u\in S_2$：
  事实上，$\text{deg}(u)$ 大于 $\sqrt m$ 的 $u$ 只有 $O(\sqrt m)$ 个：

  $$|S_2|\cdot \sqrt m<\sum_{u\in S_2}\text{deg}(u)\le 2m$$

  故 $|S_2|\le 2\sqrt m$。
  而根据连边规则，$u$ 只能向 $\text{deg}(v)\ge \text{deg}(u)$ 的点 $v$ 连边，所以 $\text{deg}(v)>\sqrt m$，故最多连 $O(\sqrt m)$ 条边。

又因为 $|E'|$ 是 $O(m)$ 的，所以该算法为 $O(m\sqrt m)$ 的。
同时，我们也证明了无向图三元环的数量是 $O(m\sqrt m)$ 的。