莫队 学习笔记

引入

莫队算法是一种优美的暴力算法，可以用来处理大量的区间询问。前提是，维护的信息可以高效地插入、删除。

我们就以一道题为例，来初探莫队：洛谷P3901 数列找不同

题意：给定一个数列，\(q\) 次询问，问区间 \([l, r]\) 内的数是否各不相同。

首先，我们很容易想到，问某个区间内的数各不相同，等价于去问这个区间的长度是否等于其中不同数的个数。那对于一个询问，我们先考虑暴力做：拿一个桶维护一下区间内每个数的个数，以及区间内不同种数的个数，从区间左侧扫到区间右侧，求出答案。但是，如果暴力去做，最后复杂度是 $q \times n $ 的，因为可能每次询问都要把整个数列扫描一遍。

我们又发现，其是我们并不需要每次都从头扫，因为有些区间的信息是重复的，那我们就要多利用重复的信息，于是就有了第二个思路：把询问离线下来，按左端点为第一关键字，右端点为第二关键字排序，用双指针来维护元素的插入和删除。这样，左端点的数就可以保证利用充分，但是，如果左端点各不相同，右端点还是会左右横跳，复杂度还是逃不过 \(q \times n\)。

现在问题就变为，如何进行排序，来让每次左右端点尽量少移动，于是就有了莫队。

思想

莫队把区间分块，把询问以左端点所在的块为第一关键字，右端点为第二关键字进行排序，让我们来看一看这样做后的复杂度：

我们设块长为 \(size\)。首先，对于每个块内的询问，每次询问后左端点最多移动 \(size\) 次，那么所有询问后左端点移动的次数就是 \(q \times size\)；然后我们来考察右端点。我们发现，在每个块内，右端点的移动都是单调不减的，可以做到线性；对于两个块之间的转换，右端点最多从最右侧移动到最左侧，也就是说，右端点最多移动 \(n \times \frac{n}{size}\) 次。又因为 \(n\) 和 \(q\) 同阶，所以最终，莫队的复杂度就是 \(O(n \times size + n\times \frac{n}{size})\)。

根据基本不懂不等式，我们发现当 \(size = \sqrt{n}\) 时，复杂度最小。所以按照 \(\sqrt{n}\) 分块，复杂度就变成 \(O(n \sqrt{n})\) 了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;

inline int read(){
    int x = 0; char ch = getchar();
    while(ch<'0' || ch>'9') ch = getchar();
    while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
    return x;
}
int bel[N];
struct Question{
    int l, r, id;
    int part;
    bool operator <(const Question &b) const{
        if(part == b.part){
            if(part & 1) return r<b.r;//玄学优化，按照奇偶性分别对右端点进行升/降序排序，让每次右端点回退最少。
            else return r>b.r;
        } else return part<b.part;
    }
}q[N];
bool ans[N];
int a[N], n;
int Q;
int l = 0, r = 0;

int vis[N], tot;
void del(int pos){
    vis[a[pos]]--;
    if(!vis[a[pos]]) tot--;
}
void add(int pos){
    if(!vis[a[pos]]) tot++;
    vis[a[pos]]++;
}

int main(){
    n = read(), Q = read();
    int lth = sqrt(n);
    for(int i = 1; i<=n; ++i) a[i] = read();
    for(int i = 1; i<=Q; ++i){
        q[i].l = read(), q[i].r = read();
        q[i].id = i;
        q[i].part = ((q[i].l-1)/lth)+1;
    }
    sort(q+1, q+Q+1);
    for(int i = 1; i<=Q; ++i){
        while(l<q[i].l) del(l++);
        while(r>q[i].r) del(r--);
        while(l>q[i].l) add(--l);
        while(r<q[i].r) add(++r);
        ans[q[i].id] = (tot == (r-l+1));
    }
    for(int i = 1; i<=Q; ++i){
        ans[i]?puts("Yes"):puts("No");
    }
    return 0;
}