神奇莫队学习笔记

· · 算法·理论

莫队算法是解决一类离线区间询问问题的分块算法。

形式

莫队算法主要用于解决单点调整操作较易的离线区间询问问题。形式化地，从 [l,r] 的答案能够以较低时间复杂度调整到 [l-1,r], [l+1,r], [l,r+1], [l,r-1] 的答案。

排序方法

记序列总长为 n，询问数为 q。

对于区间 [l,r], 以 l 所在块的编号为第一关键字，r 为第二关键字升序排序。在 n,q 同阶时，使用根号分块。

时间复杂度

以下设单点调整操作时间复杂度为 O(1)，块长为 B。

  1. 排序，此处时间复杂度 O(n \log n)；

  2. 指针调整完毕整块的时间复杂度为 O(xB)（x 为此块内部左端点个数），此处时间复杂度 O(qB)；

  3. 因为左端点同块的区间右端点有序，所以在同一块内部，右端点最劣要 O(n) 次调整（即调整整个序列），共 \displaystyle \frac{n}{B} 个块，此次时间复杂度 \displaystyle O(\frac{n^2}{B})。

共 \displaystyle O( n \log n + qB + \frac{n^2}{B}) 时间复杂度。取 \displaystyle B = \frac{n}{\sqrt q} 时时间复杂度最优，为 O(n \sqrt q)。

例题 P1972（60 pts 非正解）

// initalize blocks
int B, Bcnt, b[1001005];
void init() {  
    B = sqrt(n), Bcnt = ceil((double) n / B);
    for (int i = 1; i <= Bcnt; ++i) {
        for (int j = (i - 1) * B + 1; j <= i * B; ++j) {
            b[j] = i;
        }
    }
}
// sort queries
struct Query {
    int l, r, id;
} q[1000005];
bool operator < (Query x, Query y) {
    return (b[x.l] ^ b[y.l]) ? b[x.l] < b[y.l] : ((b[x.l] & 1) ? x.r < y.r : x.r > y.r);
} 
// solve queries
int cnt[1000005] = {}, tot = 0, ans[1000005];
void solve() {
    int l = 1, r = 0, ql, qr;
    for (int i = 1; i <= m; ++i) {
        ql = q[i].l, qr = q[i].r;
        while (l < ql) tot -= !--cnt[a[l++]];// del l
        while (l > ql) tot += !cnt[a[--l]]++;// add l
        while (r < qr) tot += !cnt[a[++r]]++;// add r
        while (r > qr) tot -= !--cnt[a[r--]];// del r
        ans[q[i].id] = tot;
    }       
}