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)
好嘛,跑得比优化一还慢。好像没法优化了,那咋办?
隆重介绍:
莫队算法
未完待续…