莫队算法简介与基本原理

莫队算法简介

莫队算法是由莫涛提出的算法．在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人．莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本．

莫队算法可以解决一类离线区间询问问题，适用性极为广泛．同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作.

问题形式

$假设 𝑛 = 𝑚 ，那么对于序列上的区间询问问题，如果从 [𝑙, 𝑟] [l, r] 的答案能够 O (1) 扩展到$
$[𝑙 - 1, 𝑟], [𝑙 + 1, 𝑟], [𝑙, 𝑟 + 1], [𝑙, 𝑟 - 1]$
$[l - 1, r], [l + 1, r], [l, r + 1], [l, r - 1]$
$即与 [𝑙, 𝑟] [l, r] 相邻的区间的答案，那么可以在 𝑂 (𝑛 \sqrt 𝑛) O (n \sqrt{n}) 的复杂度内求出所有询问的答案．$

排序方法

离线（先统计询问）后排序，按照块作为第一关键字，r作为第二关键字

何为块

先看看莫队的想法，假设有这样的查询， $[1, 6], [2, 8]$ ，我们可以这么做，我们先在 $[1, 6]$ 上做查询，然后将区间拓展到 $[2, 8]$ ，这样，我们就不用重复计算两个区间相交的部分了。我们如果让查询数组查询的右端点是升序的，右端点一定是向右边数轴右边延申的，那我们只需要关心左端点的来回移动了。但是，我们仅仅保证了右端点有序，并没保证左端点是否有序，也即，左端点是乱序的，这意味着，左端点可能从极小的数跳到极大的数，也可能从极大的数跳回极小的数，所以我们需要分块，将左端点的活动范围限制在一个一个块内。

如何分块

我们按照 $\sqrt{n}$ 的大小来将整个数组划分成若干个块，至于为什么是 $\sqrt{n}$ ，参考后面的Q & A部分。
分完块之后，我们给每个查询都打上块信息，这样，我们将左端点一块一块的分好了，接下来，保证每个块内的右端点升序，按照之前的思路就行了，这么看来，莫队算法其实是一种优雅的暴力。

复杂度分析

滑动复杂度

这里假设总查询次数m和数组长度n
我们在一个块内滑动右端点，复杂度为 $O (n)$ ，有 $\sqrt{n}$ 个块，复杂度是 $O (n \sqrt{n})$
我们在一个块内滑动左端点，假设要查询 $m_{i}$ 次，那么一个块内滑动的复杂度是 $O (m_{i} \sqrt{n})$ ，对于m个总查询，复杂度就是$$\sum_{i=1}^{m} O(\sqrt{n}) = O(m\sqrt{n})$$

块之间的切换复杂度

假设在上一个块，我们已经有了一个区间 $[l, r]$ ，不难知道， $r$ 的切换代价为 $O (n)$ ，总代价为， $O (n \sqrt{n})$
由于l总是在块内移动，所以两个块切换代价为 $O (\sqrt{n})$ ，总代价为 $O (n \sqrt{n})$
所以总切换复杂度就是 $O (n \sqrt{n})$

总复杂度

由于我们考虑 $m 、 n$ 是同阶的，所以总复杂度应该是

O (n \sqrt{n})

奇偶优化

我们将奇数块的右端点按照升序排序，偶数块右端点按照降序排序，这样，我们可以明显的减少右端点折返的次数，假如上个块是奇数块，我们来到偶数块的时候，就更有可能从较大的数下降去缩减右端点，然后减小到一个较小的数，又到达奇数块，然后从较小的数开始扩张右端点。

模板题

Talk is cheap, show me the code.—废话少说，放码过来
光说，可能不太知道是什么，还是看代码直观点

测试链接
https://www.luogu.com.cn/problem/SP3267
https://www.spoj.com/problems/DQUERY/

#include <bits/stdc++.h>
#define int long long
#define MAXQ 200005
#define MAXN 30005
#define MAXV 1000005
using namespace std;
// 习惯，查询数组与原数组都统一从1开始
int nums[MAXN];
int ans[MAXQ];
int kind = 0;
int cnts[MAXV];
void add(int num){
    if(++cnts[num] == 1){
        ++kind;
    }
}
void del(int num){
    if(--cnts[num] == 0){
        --kind;
    }
}
struct Query{
    int id, block, l, r;
    bool operator<(const Query& other) const {
        if(block != other.block){
            return block < other.block;
        }
        // 按照奇偶排序, 奇数升序
        return (block & 1) ? r < other.r : r > other.r;
    }
}querys[MAXQ];
void solve(){
    int n;
    cin >> n;
    int blockSize = ceil(sqrt(n));
    for(int i = 1; i <= n; ++i){
        cin >> nums[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; ++i){
        cin >> querys[i].l >> querys[i].r;
        querys[i].id = i;
        querys[i].block = (querys[i].l + blockSize - 1) / blockSize;
    }
    sort(querys + 1, querys + q + 1);
    int l = 1, r = 0;
    for(int i = 1; i <= q; ++i){
        int jobl = querys[i].l;
        int jobr = querys[i].r;
        while(l > jobl){
            add(nums[--l]);
        }
        while(r < jobr){
            add(nums[++r]);
        }
        while(l < jobl){
            del(nums[l++]);
        }
        while(r > jobr){
            del(nums[r--]);
        }
        ans[querys[i].id] = kind;
    }
    for(int i = 1; i <= q; ++i){
        cout << ans[i] << "\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

Q & A

Q) 为什么划分区块考虑 $\sqrt{n}$ 作为长度？
A) 为了平衡左端点移动和右端点移动的总时间复杂度。左端点（ $l$ ）移动：在同一块内，每次询问最多移动块长 $B$ 。跨越 $m$ 个询问，复杂度为 $O (m \cdot B)$ 。右端点（ $r$ ）移动：在同一块内， $r$ 是单调递增的（总计 $O (n)$ ）；共有 $n / B$ 个块，总复杂度为 $O (\frac{n}{B} \cdot n)$ 。取 $B = \frac{n}{\sqrt{m}}$ （通常简写为 $\sqrt{n}$ ）时，总复杂度 $O (m \cdot B + \frac{n^{2}}{B})$ 达到最小值 $O (n \sqrt{m})$ 。
大数据量、时限紧的比赛中，如果 $m$ 远大于 $n$ （询问很多），记得手动把块长设为 n / sqrt(m) 而不是死记硬背 sqrt(n)。
Q) 为什么是奇数块升序而不是奇数块降序?
A) 因为窗口初始不存在，对于第一个块，我们需要吸纳元素，那肯定是从小往大的扩张出有效的窗口，如果是降序的话，换句话说， $r = 0$ 作为初始值，询问的右端点当然是离初始值越近越好了，不然第一块就多扫描一次了