莫队（一）：莫队初步基础与思想

大家都看到了，我又开了个坑，没写完的记得让我填哦！

莫队算法是什么

莫队算法，是莫涛orz发明的一个优化的暴力算法，它使用看似很simple的指针移动操作以及分块的思想来将复杂度优化至$O(n\sqrt{n})$，不过首先强调：莫队是不适用与强制持续在线问题的！

首先我们先来看一道例题

这是一道莫队的模板题：https://www.luogu.org/problemnew/show/SP3267
说好了是莫队初步，我们一步一步来看。

看到题目首先想到的做法是暴力，像我这么弱的OIer看到每道题首先想到的都是暴力，dalao想到的都是正解。这个题的暴力写法非常简单，开一个大小为$10^6+10$的$bool$类型的数组，每次查询从L到R以$O(n)$的复杂度扫一遍，扫到的数字赋值$true$再扫一遍计算$true$的个数就可以了。

可以看到，这样子暴力的时间复杂度最差达到了$O(n^2)$，本题数据中$(1 ≤ q ≤ 200000)$，这个复杂度伤不起，所以我们想到优化

（敲黑板）

我们可以模拟两个指针$l$和$r$，每次询问不再是$O(n)$的枚举，而是改变$l$与$r$中间的区间，直到$[l,r]$两区间重合，在移动的过程中，我们借用扫描线的思想，区间$[l,r]$中每新增一个未曾出现的数，cnt++，每退出一个在区间内唯一存在的数,，$cnt—$，如此一来我们只需要知道一个数是否在区间内存在至少一个即可，所以可以引出另一个小优化。
/*
不过在$cnt—$前，我们必须知道是否退出的数在区间中唯一存在，因此$bool$类型不再适用，这里应该应该用一个cnt数组来记录每个数在区间中存在的个数
*/

/*
如果不了解扫描线的话可以看一下我的一篇题解，扫描线问题很简单，那道题又是一个板子，所以题解看完你就明白了：
https://www.luogu.org/blog/tongli/solution-uva1398
原题的传送门：
https://www.luogu.org/problem/UVA1398
*/

每次枚举到加入一个数$num$，判断其$cnt_{num}$是否为0，若为0则该数在区间中不曾存在，现在加入进来后，区间内不同数字的总数$tot++$。同样，每退出一个数前$num$，判断其$cnt_{num}$是否为1，若为1则该数在区间中唯一存在，退出后区间内不再有这个数，$tot—$。

如此一来，暴力已经优化掉了很多的复杂度，但是如果遇到查询的区间是这个亚子，这种优化就萎了，这个时候莫队出现了！

朴素的莫队算法

1、预处理

莫队算法的核心思想是分块，我们要将大小为$n$的序列分成$\sqrt n$个大小为$\sqrt n$的块，对每个块从$1$到$\sqrt n$编号，然后要根据编号对查询区间进行排序。排序也是莫队算法的重要基础，排序方法如下：

把查询区间的按照左端点所在的分块的序号为第一关键字，右端点本身的位置为第二关键字进行排序，然后再按照讲莫队前面的那个算法进行暴力即可。这就是莫队了是不是好简单？

//此处感谢@leiruicn的指正

一个小小的排序居然优化这么大以至于称得上算法？Amazing，Awesome！
我会在下一篇中证明莫队算法的复杂度

本篇完，见下一篇：莫队（二）：证明、代码实现和优化