U709167 【模板】普通莫队&莫队时间测试

这是莫队模板题。但是 $n,m$ 不同阶。 为了测试莫队的复杂度。 老师说是 $\mathcal O(n\sqrt{n}+m\log m)$，AI 说是 $(n+m)\sqrt{n}+m\log m$。 但是我觉得最优是 $\mathcal O(n\sqrt{m}+m\log m)$ 的。AI 这个时间复杂度一定没有 $\mathcal O(n\sqrt{m}+m\log m)$ 优（可以分 $nm$ 两种情况证明得知）。而老师说的这个时间复杂度无法达到。 显然这三者是不太一样的。此题仅做测试。

现在有一个 $n$ 个数的序列 $a_1,a_2,\dots,a_n$。 有 $m$ 次询问，每次询问 $[l,r]$ 表示 $a_l,a_{l+1},\dots,a_r$ 有多少种数字。

第一行输入 $n,m$。 第二行输入 $a_1,a_2,\dots,a_n$。 第三行到第 $m+2$ 行每行输入两个数 $l,r$，表示查询的区间。

对于每一组询问，输出种类数。

$1\leq n \leq 2\times 10^6,1\leq m \leq 10^4,1\leq l\leq r\leq n,1\leq a_i\leq n$。 made by @[GUO120822](https://www.luogu.com.cn/user/704562)。 证明可以看这里： 首先的想法是按左端点排序。但这样左端点移动次数是 $\mathcal O(n)$ 的，右端点是 $\mathcal O(n^2)$ 的。不太平衡。 考虑按左端点分块。设块长为 $B$。那么一共有 $\frac{n}{B}$ 个块，对于每一个块，按右端点排序，每一个块右端点移动次数是 $\mathcal O(\frac{n^2}{B})$ 的。对于左端点，对于相邻的两个，差不超过 $B$，移动 $\mathcal O(mB)$ 次。对于不同的相邻的块，总移动次数为 $\mathcal O(\frac{n^2}{B})$ 次。再加上排序，然后总复杂度为 $\mathcal O(\frac{n^2}{B}+mB+m\log m)$。 如何使这个值最小？均值不等式。$\frac{n^2}{B}+mB\geq \sqrt{n^2m}=n\sqrt{m}$，仅当 $\frac{n^2}{B}=mB$ 即 $B=\frac{n}{\sqrt{m}}$ 时取等。 最终结论：取 $B=\frac{n}{\sqrt{m}}$ 最优，时间复杂度为 $\mathcal O(n\sqrt{m}+m\log m)$。 所以如果你超时了，不妨试一试把 $B$ 改成 $\frac{n}{\sqrt{m}}$ 吧。