普通莫队学习

莫涛队长算法学习笔记~~(之前一直以为莫队是一种(莫氏)队列233)~~

简介

号称可以解决一切区间类问题的莫队算法。可以在$O(n \sqrt{n})$的复杂度内解决离线区间查询类问题。
其比线段树等数据结构的优越性在于可以处理一些不满足区间可加性的问题，如:区间众数等问题。

算法思路与实现

给出一个有n( n < 30000 )个数的数列，每个数小于1e6。给出q次询问( q < 200000 )，每次询问l到r有多少个不同的数？ (题目链接：SPOJ - D-query)

暴力O(n^2)

暴力做法很显然，即就是对于每一次查询，循环遍历整个区间，数一数数。

暴力代码

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1000000 + 10 ;
int a[maxn];
 
int main()
{
    int n ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i++)
        cin >> a[i];
    int q;
    cin >> q ;
 
    while(q--)
    {
        int l , r ;
        cin >> l >> r ;
        int cnt[maxn];
        int ans = 0 ; 
        memset( cnt , 0 , sizeof( cnt ) ) ; 
        for( int i = l ; i <= r ; i++)
        {
            cnt[ a[i] ]++;
            if( cnt[ a[i] ] == 1 )
                ans++;
        }
        cout << ans << endl ;
    }
    return 0 ;
}

换种方式的暴力

我们把暴力方法进行修改，就是换种写法。但是我们上面的做法是每次都是从L循环到R，这一次我们尝试着的是从上一次的查询位置，调整到这一次的查询位置。
也就是说，如果上一次查询是[1,5]，这一次的查询范围是[2,4]。下一次我们将尝试从[1,5]的答案，调整转移到[2,4]的答案。如何转移呢？也就是说我们先考虑左端点，我们把左端点要从1移动到2，那么就要删除1这个元素。右端点我们要从5调整到4，也就是要删除第5个元素。
我们就是这样不断调整到这一次的查询上。
当然，我们会发现这种方法和上一种方法相比，没有什么更优(除了一些常数差异)

换种暴力

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1000000 + 10 ;
int a[maxn];
int cnt[maxn];
int ans = 0 ; 
 
void add( int pos ) 
{
    cnt[ a[pos] ]++;
    if( cnt[ a[pos] ] == 1 )
        ans++;
}
 
void remov( int pos )
{
    cnt[ a[pos] ]--;
    if( cnt[ a[pos] ] == 0 )
        ans--;
}
 
 
int main()
{
    int n ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i++)
        cin >> a[i];
    int q;
    cin >> q ;
 
    int l = 0  , r = 0 ; 
    while(q--)
    {
        int ll , rr ;
        cin >> ll >> rr ;
        while( l < ll )
            remov(l++);
        while( l > ll )
            add(--l);
        while( r < rr )
            add(++r);
        while( r > rr )
            remov(r--);
 
        cout << ans << endl ;
    }
    return 0 ;
}

莫涛队长算法

莫队算法相比我们换种方式的暴力，仅仅是调整了每一次查询的顺序(离线处理)。我们现在有q个查询，将把查询进行一些调整后再处理。
具体的调整是：

我们将给定的数组的n个元素进行分块，分成$\sqrt{n}$块，每一块内有元素$\sqrt{n}$块。
显然左右端点都会落入某一块中，我们考察左端点所在的块号，按照块号从小到大进行排序(第一关键字)。
在每一块内，我们按照r端点从左到右进行排序(第二关键字)。

如此，我们便完成了莫涛队长算法。核心仅仅在于调整了查询的顺序，变成了优雅地暴力。

ACcode

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 300000 + 100 ;
const int maxm = 1000000 + 10 ;
int a[maxn];
int cnt[maxm];
int ans = 0 ; 
int BLOCK = 0 ;
 
inline void add( int pos ) 
{
    cnt[ a[pos] ]++;
    if( cnt[ a[pos] ] == 1 )
        ans++;
}
 
inline void remov( int pos )
{
    cnt[ a[pos] ]--;
    if( cnt[ a[pos] ] == 0 )
        ans--;
}
 
struct QUERY
{
    int l , r , num ;
}Q[maxn];
 
int ANS[maxn];
inline bool cmp( const QUERY &a , const QUERY &b )
{
    if( a.l / BLOCK != b.l / BLOCK )
        return a.l / BLOCK < b.l / BLOCK ;
    else
        return a.r < b.r ;
}
 
int main()
{
    int n ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i++)
        scanf("%d",&a[i]);
    int q;
    scanf("%d",&q);
 
    for( int i = 1 ; i <= q ; i++)
    {
        int l , r ;
        scanf("%d%d",&l,&r);
        Q[i].l = l , Q[i].r = r , Q[i].num = i ;
    }
    BLOCK = sqrt(n);
    sort( Q + 1 , Q + 1 + q , cmp ) ;
    int l = 0  , r = 0 ; 
    for( int i = 1 ; i <= q ; i++)
    {
        int ll = Q[i].l  , rr = Q[i].r;
        while( l < ll )
            remov(l++);
        while( l > ll )
            add(--l);
        while( r < rr )
            add(++r);
        while( r > rr )
            remov(r--);
        ANS[Q[i].num] = ans ; 
    }
 
    for( int i = 1 ; i <= q ; i++)
        printf("%d\n",ANS[i]);
    return 0 ;
}

时间复杂度的证明

我们先考虑左指针如何移动。对于每个块，所有查询都落在同一个块内，每次查询，左指针都会在块内进行移动，移动范围不超过$\sqrt{N}$。Q次询问，则复杂度为$O( Q * \sqrt{N})$
我们在考虑右指针如何移动。对于每个块内，右端点递增排序，右指针最多移动N次(可能从上一个块查询到整个数列的最末端再移动到当前块的最前端，但这依然不过是2N次)，一共有$\sqrt{N}$个块，所以复杂度最多为$O( N * \sqrt{N} )$次
总复杂度: \[ O( Q * \sqrt{N} + N * \sqrt{N} ) = O( N * \sqrt{N} ) \]

总结

莫队算法可以解决的是由[l,r]区间的答案可以很方便的转移到[l+1,r] , [l-1,r],[l,r+1],[l,r-1]等范围的答案(通常上是O(1)转移，也可O(logn)转移，此时复杂度多一个logn)。
之所以博客叫普通莫队，是因为莫队还有带修改莫队，树上莫队等等...
据说有通过合理调整分块大小，可以解决n和m不同的情况。 > 莫队复杂度为$O(n\sqrt{n} + n\sqrt{m})$，不过在这情况下，分块需要调整为$ $

参考资料

第一个参考资料非常好，可惜是英文的qwq.