根号算法学习笔记

EchoHua0402 · 2025-11-16 12:36:46 · 算法·理论

分块

一般用来解决区间问题。

我们考虑把区间分成若干块，对于每个我们维护该块的信息。

例如：

有 Q 次操作：

我们可以维护每个块的和。设块长为 S。那么对于每个操作，我们需要访问 [l,r] 包含的所有块以及 l,r 所在的散块，单次操作的复杂度为 O(S+\frac{n}{S})。

由均值不等式可知，当 S=\frac{n}{S} 时最优，所以最优的块长为 S=\sqrt{n}，此时单次操作的复杂度为 O(\sqrt{n})。

根号分治

在有些题目中，我们有多种暴力的方式，而每种暴力的效率与我们每次的查询有关。于是我们可以根据某个阀值 S 采用不同方式的暴力。

这样说还是有点抽象了，还是结合例题说一下会比较清楚。

例题：P3396

我们有两种暴力方式：

1. 每次询问暴力 O(\frac{n}{x}) 的一个一个跳。这样的话，查询操作会在 x 很小的时候卡到 O(n)，而每次修改是 O(1) 的。
2. 维护一个数组 sum_{i,j}，表示下标模 i 余 j 的数的和。每次修改的时候，我们修改 sum_{i,x\%i}，其中 i 为后面的查询中最大的 x。这样的话，修改操作会在 i 很大的时候卡到 O(n)，而每次查询是 O(1) 的。

我们想在这两种暴力之间找到一个平衡点，于是我们根据 x 与 \sqrt{n} 的大小关系，分开治理。

1. 维护数组 sum_{i,j}，意义与上述第二种暴力相同，但我们只维护 i \le \sqrt{n} 的模数 i。
2. 对于每次查询，如果 x \le \sqrt{n}，直接输出 sum_{x,y}，复杂度 O(1)；否则，暴力 O(\frac{n}{x}) 的跳过去，复杂度 O(\sqrt{n})。
3. 每次修改，更新 sum_{i,x\%i}，复杂度 O(\sqrt{n})。

总复杂度 O(m \sqrt{n})。

总结：一般来说当暴力复杂度跟区间长度、字符串长度有关的时候，就可以考虑用数组或其他数据结构来维护 \le 或 \ge \sqrt{n} 的部分，然后另一部分直接暴力，使单次复杂度不超过 O(\sqrt{n})。

这就是优雅的暴力~

莫队

普通莫队

如果 [l+1,r]，[l-1,r]，[l,r+1]，[l,r-1] 的答案均可以由 [l,r] 的答案 O(1) 修改得到的话，那么该问题就可以用莫队算法来解决。

考虑分块。

我们对于每一个查询操作离线下来，然后按照查询区间的 l 所在的块为第一关键字，按 r 为第二关键字排序。排序后维护一个 [L,R]，表示已经处理好的区间，对于当前查询的区间，直接暴力跳过去，记录下答案即可。

这个东西大概长成这个样子：

while (R<r) Add(++R);
while (R>r) Delete(R--);
while (L>l) Add(--L);
while (L<l) Delete(L++);

//其中Add()表示加贡献，Delete()表示减贡献

模板题：P1494

掌握上述流程之后其实就不难。

设当前要加或减的袜子的颜色是 c，则它所带来的贡献就是 cnt_c，其中 cnt_c 表示颜色 c 的数量。（这个可以组合数把式子展开来证，但是可以简单一点：多出来的贡献可定是要钦定选择当前的袜子的，那么为了配对成功，就需要从之前的颜色为 c 的袜子里选一个，所以有 cnt_c 种选择，贡献就是 cnt_c。）弄一个全局的 ans 来记录答案就行。

复杂度

R 的移动

首先对于每一个块，求出其第一个询问的答案需要 O(n) 的时间，由于同一个块中的 r 是排好序的，所以在同一个块中从第一个求到最后一个 r 需要 O(n) 的时间，那么 \sqrt{n} 个块就是 O(n\sqrt{n})。

块与块之间的 r 是无序的，所以每次移动最坏为 O(n) 的，但由于块是排好序的，且有 \sqrt{n} 个块，所以这样的移动最多只有 O(\sqrt{n}) 次，复杂度为 O(n\sqrt{n})。

所以 R 移动的复杂度为 O(n\sqrt{n})。

L 的移动