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)
好嘛,跑得比优化一还慢。好像没法优化了,那咋办?

隆重介绍:

莫队算法

未完待续…

Last modified: 2020年11月29日

Author

Comments

Write a Reply or Comment