撰写目录
大家都看到了，我又开了个坑，没写完的记得让我填哦！
莫队算法是什么
莫队算法，是莫涛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！
我会在下一篇中证明莫队算法的复杂度
wpDiscuz