根号暴力专题 - 洛谷保存站

注：根号暴力算法指一些时间复杂度为 $O(n\sqrt n)$ 的较为暴力的算法，通常情况下在 $n\le 10^5$ 级别时可以通过。

# 1. 普通莫队

其基本思想基于分块的性质，主要解决线段树等其他较为优秀的数据结构较难实现的**离线区间**问题。

首先这个问题需要满足：对于区间 $[l,r]$ 的维护是可以以 $O(1)$ 的时间复杂度将左 $/$ 右端点向左 $/$ 右移一格的，移动到 $[l±1,r]$ 活着 $[l,r±1]$。

于是我们可以按照顺序依次处理每个询问。

问题在于，题目给定的询问区间顺序不一定是最优的，有可能出题人使用 $\texttt{秘技——反复横跳}$ 来使你的 $l,r$ 相邻两个相差极大，给你卡到 $O(n^2)$ 了。就算你按照 $l$ 或 $r$  排序后他依旧可以使用 $\texttt{秘技——反复横跳}$。我们需要一些更优秀的给区间排序的方法。

于是分块大神登场！

假设我们以 $X$ 为块长，将所有的 $l$ 分为 $\dfrac{N}{X}$ 块，对于所在块相同的 $l$ 我们将其对应的 $r$ 排序，不同的我们再按照 $l$ 排序。

考虑最坏情况，假设所在块相同的 $l$ 在这块里面 $\texttt{秘技——反复横跳}$，最多每次需要 $O(X)$，总共是 $O(N\times X)$。而 $r$ 假设每一块末尾到下一段开头都是 $N\to 1$，最多需要 $O(N)$，而总共有 $\dfrac{N}{X}$ 段，所以总共是 $O(N\times\dfrac{N}{X})$，$l,r$ 加起来是 $O(N\times(X+\dfrac{N}{X}))$，要使其最小解之得 $X=\sqrt{N}$。

所以总的时间复杂度就是 $O(N\sqrt{N})$。

当然你也可以写曼哈顿距离最小生成树，但是我不会。会了也不会莫队。

## 例题：小 Z 的袜子

### 题意

给定一个长度为 $n$ 的序列 $C_i$，每次询问一个区间 $[l,r]$ 求从区间内选择任意两个位置不同的数，相等的概率是多少。

### 思路

按每个颜色 $i$ 考虑。记区间内出现颜色 $i$ 的个数为 $cnt_i$，概率应该为 $\dfrac{\sum\limits_{i\in C}C_{cnt_i}^2}{C_{r-l+1}^2}=\dfrac{\sum\limits_{i\in C}cnt_i^2 - (r - l + 1)}{(r-l+1)\times (r-l)}$。那么我们需要维护区间内每种颜色出现次数的平方和。

结合我们刚刚讲到的莫队知识，我们是可以 $O(1)$

正在渲染内容...