Q：莫队是什么？
A：莫队是由前国家队队长莫涛提出的一种毒瘤玄学且暴力，同时期望时间复杂度惊人地优秀的算法。

今天我们来学习他的基础形态(的前置知识)。

引入

洛谷SP3267 DQUERY-D-query

题目梗概：
给定一长度为n的序列，有m次查询，每次询问[L，R]内不相同数的个数。
数据范围：
n≤30000
m≤200000

建议思考一段时间想想怎么做。最好写出你认为最优秀的算法并计算时间复杂度。

你写了个主席树？那你还待在这学普通莫队干什么玩意儿？

咳咳，好的。这题的正解如上所说是O(nlogn)的主席树。然而我们今天要来学习这题的另一种解法，也就是O(n√n)的莫队算法。

先从最简单的方法说起

也就是最暴力的暴力。

用一个数组cnt记录每个数出现的次数，对于每个区间枚举从L到R进行统计，最后再扫一遍cnt得到出现次数非零的数的个数。

时间复杂度：O(m(n+maxx))，其中maxx表示出现的最大数。显然复杂度直接起飞，要跑到1s内建议去借用一下天河二号。

思考如何优化

暴力美学中的美来自这里。

优化一

每枚举到一个数x（添加一个数），判断cnt[x]是否等于0，为0则代表没出现过，数的种类多了一种，若不为0则代表以前出现过，种类数不变。
ex.删除一个数（之后要用）：删除一个数后，检验该数个数是否为0，为0则种类数少了一个。
经此优化，每次遍历完一个区间后不需要再扫一遍cnt就能得到出现了多少个不同的数。

void add(int p)//添加p位置上的数
{
    if(!cnt[a[p]])//若当前位置上的数没出现过
    {
        cat++;//cat=category种类  则种类数+1
    }
    cnt[a[p]]++;//该数出现次数+1
}
void del(int p)//删除p位置上的数
{
    cnt[a[p]]--;//该数出现次数-1
    if(!cnt[a[p]])//若该数-1后已经一个不剩（刚刚删除的为最后一个）
    {
        cat--;//种类数-1
    }
}

减少了O(m*maxx)，还远远不够。

优化二

显然在我们之前的程序里，如果区间有重叠，而我们仍然每次从一个区间的开头开始统计的话，我们将会消耗时间做一些重复的工作。

给点思考时间。

我们考虑使用双指针的技巧。
设序列上有两指针lp左指针，rp右指针，lp一般小于rp。（此时cnt用于记录lp至rp之间序列的数据）每次进行统计的时候我们不再从区间开头开始，而是用lp和rp从他们所在位置（lp，rp之间的区间已经进行过统计）移动，分别去“够”每个区间的左右端点，在移动时套用优化一的方法进行更新。
显然如果两区间重合度高的话，我们用这个优化可以省下许多时间。

移动指针时又有以下四种情况：

设要到的区间左端点为L，右端点为R
若L<lp，即左端点在左指针左边
我们需要将左指针一直移动，直到到达左端点为止。当前左指针上的数值仍在左右指针的区间内，因此不需要删除，只需要将lp左移，并将左移后lp上的数添加入数据即可。

lp--;       //指针左移，不需要删除
add(lp);    //将左移后lp上的数添加进数据

同理：
若R>rp，即右端点在右指针右边。
先右移，再添加。

rp++;       //先右移
add(rp);    //再添加

若lp<L，即左端点在左指针右边。
lp当前所在位置上的数将不再存在于指针区间中，故我们先将lp上的数删除，再将lp右移。

del(lp);
lp++;

同理：
若R<rp，即右端点在右指针左边。
先删除，再左移。

del(rp);
rp--;

优化二就此达成。

然而这种做法有一个明显的问题。
考虑：若不同区间的左右端点相隔非常远，每次移动都得跨越整个序列，那么时间复杂度会是多少。
O(nm)
好嘛，跑得比优化一还慢。好像没法优化了，那咋办？

隆重介绍：

莫队算法

未完待续…