普通莫队

"莫队算法"是用于一类离线区间询问问题的常用算法，以适用性广、代码量短、实际运行速度快、适合骗分等优点著称。　　　　　　　　　　　——莫涛

莫队的基本操作基于暴力实现，其降低复杂度的突破口在于处理“询问”。通过对询问合理的排序，使得之后的询问充分利用先前询问得到的信息，可以将 \(O(NM)\) 的复杂度显著降低至 \(O(N \sqrt{M})\) 。确实是适合骗分的好算法。

以下题为例：

Acwing2492 HH的项链
长度为 \(N\) 的序列，\(M\) 次询问，每次询问一段闭区间内有多少个不同的数。\(1≤N≤50000\)，\(1≤M≤2×10^5\)。

先考虑暴力做法。对于每次操作，从 \(L\) 到 \(R\) 扫一遍，统计个数。但我们想，对于一些左右端点都相近区间，这样的做法显然浪费了很多可以利用的数据。
于是再考虑另一种暴力做法。用两个指针 \(i\),\(j\) 标记左右区间，对于一个新的查询，只需移动这两个指针到新的位置即可。这样保留的可以利用的数据，不用重新扫描。但又很容易发现新的问题：对于两个相距很远的区间，移动指针仍然需要 \(O(N)\)。只需稍加构造，复杂度仍为 \(O(NM)\)。此时，先前区间维护的信息也不能很好地传递给之后相近的区间，而是被中间的其他区间浪费掉了。
若我们将所有区间按右端点排序，则右端点指针仅会移动至多 \(N\) 次。这种单调性给我们启发。如果能再将所有相近的左端点维护在一起，那么不就解决了以上问题吗？
莫队维护相近左端点的方法是分块。设每块长度为 \(S\)，共 \(\frac{N}{S}\) 块。将所有区间按照 \(L\) 所属块排序，\(L\)所属块相同时再按 \(R\) 递增排序。在这样的顺序下，执行上述暴力做法。然后我们再来分析时间复杂度：

• 左端点指针：块内移动每次为 \(O(S)\)，移动 \(M\) 次；块间移动每次为 \(O(S)\)，移动 \(\frac{N}{S}\) 次。共 \(O(SM+N)\)。
• 右端点指针：对于左端点所属的每个块，每次 \(O(N)\)，移动 \(\frac{N}{S}\) 次。共 \(O(\frac{N^2}{S})\)。

总时间复杂度为 \(O(SM+N+\frac{N^2}{S})\)。其中 \(N\) 一定小于 \(\frac{N^2}{S}\)，可以忽略。利用基本不等式，\(SM+\frac{N^2}{S}≥\sqrt{N^2M}\)，其中 \(N\),\(M\)是常数，故最小值在 \(SM\) 与 \(\frac{N^2}{S}\) 相等时取得。于是得到 \(S=\sqrt{\frac{N^2}{M}}\) 时，复杂度取最小值，值为 \(O(N\sqrt{M})\)。

Code

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 5e4 + 5;
const int M = 2e5 + 5;
const int L = 1e6 + 5;
int n, a[N], m, len, pos[N];
int cnt[L], res, ans[M];
struct Query {
    int id, l, r;
    bool operator <(const Query &oth) const {
        return pos[l] == pos[oth.l] ? r < oth.r : pos[l] < pos[oth.l];
    }
} q[M];
void add(int x) {
    if (!cnt[a[x]]) res++; cnt[a[x]]++;
}
void del(int x) {
    cnt[a[x]]--; if (!cnt[a[x]]) res--;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = (Query){i, l, r};
    }
    len = max(1, (int)sqrt((double)n * n / m));
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    sort(q + 1, q + m + 1);
    for (int k = 1, i = 0, j = 1; k <= m; k++) { //i右j左
        while (i < q[k].r) add(++i);
        while (i > q[k].r) del(i--);
        while (j < q[k].l) del(j++);
        while (j > q[k].l) add(--j); //这四个while十分浓缩，建议纸上推一遍
        ans[q[k].id] = res;
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

带修莫队

顾名思义，就是可以修改序列数值的莫队。
例：Acwing2521 数颜色
题意：就是上题+修改操作。
普通的莫队，处理的是一维问题(序列)。我们在这里增加一个维度表示时间，时间轴的单位为每次修改操作。即每次修改之后，都有一个新的序列与之对应。此时查询操作为查询特定时间时的区间信息，显然可以离线。
此时莫队由一维变成了二维，我们也可以用相似的方法处理。先对序列分块，每块大小为 \(S\)。此时询问有三元：(\(L,R,t\))。先将所有询问按照 \(L\) 所属块排序，相同时按照 \(R\) 所属块排序，最后按照 \(t\) 递增排序。此时设三个指针：右指针 \(i\)，左指针 \(j\)，时间指针 \(t\)。指针移动一单位均为 \(O(1)\)。分析复杂度：

• \(j\)：与普通莫队相似，\(O(SM+N)\)。
• \(i\)：块内移动 \(O(S)\)，\(M\) 次；块间移动 \(O(N)\)，\(\frac{N}{S}\) 次。共 \(O(SM+\frac{N^2}{S})\)。
• \(t\)：设共修改 \(T\) 次。\(i\) 块间移动 \(\frac{N}{S}\) 次，\(j\) 块间移动 \(\frac{N}{S}\) 次，每次 \(t\) 移动为 \(O(T)\)。共 \(O(\frac{N^2T}{S^2})\)。

相加，忽略 \(N\) 及常数，则为 \(O(MS+N^2S^{-1}+N^2TS^{-2})\)。数学不好，过程推不来……结论是，当 \(M\) 与 \(N\) 处于同一个数量级时，最小值为 \(O(\sqrt[3]{N^4T})\)，当 \(S=\sqrt[3]{NT}\) 时取得。
另外，\(t\) 指针会上下移动，故要维护好修改操作，并支持向下移动。小技巧详见代码。

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e4 + 5;
const int L = 1e6 + 5;
int n, m, w[N], mc = 1, mq, pos[N];
int p[N], c[N], cnt[L], res, ans[N];
struct Query {
    int id, l, r, t;
    bool operator <(const Query &oth) const {
        return pos[l] != pos[oth.l] ? pos[l] < pos[oth.l] : (pos[r] != pos[oth.r] ? pos[r] < pos[oth.r] : t < oth.t);
    }
} q[N];
void add(int x) {
    if (!cnt[x]) res++; cnt[x]++;
}
void del(int x) {
    cnt[x]--; if (!cnt[x]) res--;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    while (m--) {
        char opt[5];
        int a, b;
        scanf("%s%d%d", opt, &a, &b);
        if (opt[0] == 'Q') q[++mq] = (Query){mq, a, b, mc};
        else p[++mc] = a, c[mc] = b;
    }
    int len = max(1, (int)cbrt((double)n * mc)); //cbrt开三次根号。也可用pow(值,1.0/3)
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
    sort(q + 1, q + mq + 1);
    for (int k = 1, i = 0, j = 1, t = 1; k <= mq; k++) {
        int l = q[k].l, r = q[k].r, tt = q[k].t;
        while (i < r) add(w[++i]);
        while (i > r) del(w[i--]);
        while (j < l) del(w[j++]);
        while (j > l) add(w[--j]);
        while (t < tt) {
            ++t;
            if (j <= p[t] && p[t] <= i) {
                del(w[p[t]]); add(c[t]);
            }
            swap(w[p[t]], c[t]); //小技巧来了
        }
        while (t > tt) {
            if (j <= p[t] && p[t] <= i) {
                del(w[p[t]]); add(c[t]);
            }
            swap(w[p[t]], c[t]);
            --t;
        }
        ans[q[k].id] = res;
    }
    for (int i = 1; i <= mq; i++) printf("%d\n", ans[i]);
    return 0;
}