普通莫队基本思想

莫队基本可解决一切区间查询的问题.

普通莫队常用于维护区间答案，比如：对于一个长度为 n 的序列，给出 m 次询问，每次询问区间 [l,r] 内有多少个不同的颜色，其中 n,m<=100000.

先考虑暴力的方法，对于每个询问，我们都去遍历统计一遍，复杂度 $\text{[math]}$

换一种暴力的方式,我们用左右端点两个指针维护这个区间。然后思考每次移动指针对答案的贡献。

但是我们很容易构造出一组数据使得每次指针还是可能移动O(n),复杂度还是 $\text{[math]}$ .

到这我们很自然就想到了先把所有询问读入进来，然后对询问区间进行某种排序使得左右指针挪动次数尽量少.(强制离线)

算法复杂度的分析:两个部分:分块,排序

1.分块

①当n,m同阶的时候,容易证明将长度为n的序列分为 $\sqrt{n}$ 块最优。那么每个块中均摊有 $\sqrt{n}$ 个询问的左端点，我们可以保证其右端点有序，那么在最差的情况下

每次询问左端点最多移动 $\sqrt{n}$ ,共有 $\sqrt{n}$ 个左端点,那么左端点移动的距离为 n

右端点由于是升序,移动的距离也是 n .

总共有 $\sqrt{n}$ 个块，设转移的复杂度为O(1),那么总复杂度为 $O(n\sqrt{n})$ .

*更进一步分析:

根据上面的分析我们知道:莫队算法的复杂度主要来自于区间左右两端移动的复杂度。

现在设我们要分块的长度为S,那么总共有n/S个块，设m,n同阶，即n ≈ m时,数据随机的情况下,每个块内的区间查询的个数为n^2 /S。这个时候我们采用这样一个策略（做一个这样的取舍），因为这些块的左端点反正都在聚集在同一个块内了，不会移动太多距离，但是右端点没有保证，所以在左端点在同一个块的情况下，我们保证右端点升序就好了。

那么分别计算左右两个端点移动所产生的复杂度:

右端点，根据上面的分析我们知道:右端点是升序了的,那么它所带来的复杂度为:O(n)

左端点，考虑最差的情况，最差的情况是，在保证右端点升序的情况下，左端点在块的两端来回跳动.这样复杂度是最高的。

那么总共有n/S个块，总共有n次询问，那么一个块内的询问个数为S.块的长度为S,那么左端点移动的复杂度为O(S^2).

总复杂度为O(S^2 + n),这是一个块的情况，那么总共有n/S个块，那整体复杂度为:O(n^2/S + n*S).现在我们面临的问题是什么？是到底S分块分为多长使得这个总体复杂度最优，那么它就是一个关于S的函数，我们现在要求最小值。对其求导易知,当S = sqrt(n)时，总体复杂度取最优，为O(nsqrt(n)).

②当询问次数m远大于n的时候,

2.排序

根据上面的分析我们知道,排序时优先左端点排序，若左端点在同一个块内，则右端点升序排序.即以左端点为第一关键字，以右端点为第二关键字.

考虑优化

我们知道，处理完一个块以后，右端点移动到最右边,那么进入下一个块的时候右端点又要从右移动到最左边，多了一些无谓的移动。那么自然就有一个想法，按块的奇偶排序。即，块为奇数时右端点升序排序，块为偶数时，右端点降序排序.理论上速度快一倍.