莫队算法

前置知识

分块思想

目标

普通莫队算法

What

对于序列上的区间询问问题，离线后排序，顺序处理每个询问，暴力从上一个区间的答案，转移到下一个区间的答案。[l, r] 的答案，可以 �(1) 的时间，扩展到 [l - 1, r], [l + 1, r], [l, r + 1], [l, r - 1]的答案，那么就可以用莫队算法，在 �(��) 的时间复杂度求解。

例题，SPOJ-DQUERY

题意，m次询问，每次询问，输出[l, r]区间内，有多少个不同的数字

#include <bits/stdc++.h>

using namespace std;

const int N = 30010, M = 2e5 + 10, SIZE = 1e6 + 10;

int a[N], n, m;
int B; // Block-size
int l = 1, r = 0, now; // the initial number, l = 1, r = 0, like queue, like slide-window
int ans[M]; // record offline answer
int cnt[SIZE]; 

struct mo {
    int l, r, id;

    bool operator< (const mo &W) const{
        if (l / B != W.l / B) return l < W.l;

        // Constant optimization
        // in odd block, the r point, left -> right
        // in even block, the r point, left <- right
        if ((l / B) & 1) return r < W.r;
        return r > W.r;
    }
}q[M];

void add(int p) {
    if (cnt[a[p]] == 0) now++;
    cnt[a[p]]++;
}

void del(int p) {
    cnt[a[p]]--;
    if (cnt[a[p]] == 0) now--;
}

int main() {
    cin >> n;
    B = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];

    cin >> m;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }

    sort(q, q + m);

    for (int i = 0; i < m; i++) {
        while (l > q[i].l) add(--l);
        while (r < q[i].r) add(++r);
        while (l < q[i].l) del(l++);
        while (r > q[i].r) del(r--);
        ans[q[i].id] = now;
    }

    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);

    return 0;
}

题单

SPOJ-DQUERY [P1972 SDOI2009] HH的项链 P2709 小B的询问 CF617E XOR and Favorite Number P3709 大爷的字符串题

总结

访问莫队本人的知乎，点击：莫涛 Orz... 观摩学习真正的大佬

参考

普通莫队算法 - OI Wiki Pecco：算法学习笔记(24): 莫队 莫队算法--从入门到黑题 - WAMonster - 博客园 浅谈一类“暴力”在OI中的应用--莫队 - DPairの博客 - 洛谷博客