复杂度分析

aa：块长，nn：数组长度，mm：询问个数，tt：修改个数。

普通莫队

Luogu P1494 [国家集训队]小Z的袜子

  1. 各指针复杂度（从上往下依次代表左端点，右端点，时间点的移动次数）

    am+n                   n×naam+n\\ ~~~~~~~~~~~~~~~~~~~n\times\dfrac{n}{a}\\

  2. 最优块长（nn，mm，tt 同阶情况下）

    nm\dfrac{n}{\sqrt{m}}\\

带修莫队

Luogu P1903 [国家集训队]数颜色 / 维护队列

  1. 各指针复杂度

    am+n         am+n×na                          t×(na)2am+n\\ ~~~~~~~~~am+n\times\dfrac{n}{a}\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~t\times\left(\dfrac{n}{a}\right)^2

  2. 最优块长

    n23n^{\frac{2}{3}}\\

回滚莫队

AT1219 歴史の研究

  1. 各指针复杂度

    am                     n×naam\\ ~~~~~~~~~~~~~~~~~~~~~n\times\dfrac{n}{a}\\

  2. 最优块长

    nm\dfrac{n}{\sqrt{m}}\\

树上莫队

SP10707 COT2 - Count on a tree II

复杂度与相当于普通莫队。

二次离线莫队

Luogu P4887 【模板】莫队二次离线（第十四分块(前体)）

复杂度与相当于普通莫队的复杂度加上二次离线的复杂度。

代码

普通莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int lenpart, inpart[MAXn + 10];
void EvaInpart(int n, int m) {
    lenpart = ceil((double)n / sqrt(ceil((double)m)));
    for (int i = 1; i <= n; ++i) {
        inpart[i] = i / lenpart;
    }
}

struct Query {
    int l, r, id;
    inline bool operator<(const Query sec) const {
        if (inpart[l] == inpart[sec.l]) {
            return inpart[l] & 1 ? r < sec.r : sec.r < r;
        }
        return l < sec.l;
    }
} que[MAXm + 10];

int n, m, a[MAXn + 10];
int sum, buc[MAXc + 10], ans[MAXm + 10];
inline void add(int v) {/* ... */}
inline void del(int v) {/* ... */}
void Mocap() {
    for (int i = 1, l = 1, r = 0; i <= m; ++i) {
        while (l > que[i].l) add(a[--l]);
        while (r < que[i].r) add(a[++r]);
        while (l < que[i].l) del(a[l++]);
        while (r > que[i].r) del(a[r--]);
        // 记录答案
    }
}

带修莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int lenpart, inpart[MAXn + 10];
void EvaInpart(int n) {
    lenpart = ceil((double)cbrt((double)n) * cbrt((double)n));
    for (int i = 1; i <= n; ++i) {
        inpart[i] = i / lenpart;
    }
}

struct Query {
    int l, r, t, idx;
    inline bool operator<(const Query sec) const {
        if (inpart[l] == inpart[sec.l]) {
            if (inpart[r] == inpart[sec.r]) {
                return t < sec.t;
            }
            return inpart[l] & 1 ? r < sec.r : sec.r < r;
        }
        return l < sec.l;
    }
} que[MAXquery + 10]; int cntque;
struct Change {
    int p, v;
} cha[MAXchange + 10]; int cntcha;

int n, m, a[MAXn + 10];
int buc[MAXcolor + 10], res;
int ans[MAXn + 10];
inline void add(int v) {/* ... */}
inline void del(int v) {/* ... */}
void Mocap() {
    for (int i = 1, l = 1, r = 0, t = 0; i <= cntque; ++i) {
        while (que[i].l < l) add(a[--l]);
        while (que[i].r > r) add(a[++r]);
        while (que[i].l > l) del(a[l++]);
        while (que[i].r < r) del(a[r--]);
        while (que[i].t > t) {
            if (cha[t + 1].p >= l && cha[t + 1].p <= r) {
                del(a[cha[t + 1].p]);
                add(cha[t + 1].v);
            }
            swap(a[cha[t + 1].p], cha[t + 1].v);
            ++t;
        }
        while (que[i].t < t) {
            if (cha[t].p >= l && cha[t].p <= r) {
                del(a[cha[t].p]);
                add(cha[t].v);
            }
            swap(a[cha[t].p], cha[t].v);
            --t;
        }
        ans[que[i].idx] = res;
    }
}

回滚莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int lenpart, inpart[MAXn + 10];
void EvaInpart(int n, int m) {
    lenpart = ceil((double)n / sqrt((double)m));
    for (int i = 1; i <= n; ++i) {
        inpart[i] = i / lenpart;
    }
}

int n, m, a[MAXn + 10];
int cntmap, mapup[MAXn + 10]; map<int, int> mapdown;
struct Query {
    int l, r, idx;
    inline bool operator<(const Query sec) const {
        if (inpart[l] == inpart[sec.l]) {
            return r < sec.r;
        }
        return l < sec.l;
    }
} que[MAXm + 10];

int buc[MAXn + 10], res, ans[MAXm + 10];
inline void add(int v) {/* ... */}
void Mocap() {
    for (int i = 1, j = 1; i <= m; i = j) {
        while (j <= m && inpart[que[i].l] == inpart[que[j].l]) ++j;
        int k = i;
        for (; k < j; ++k) {
            if (inpart[que[k].l] == inpart[que[k].r]) {
                for (int p = que[k].l; p <= que[k].r; ++p) add(a[p]);
                ans[que[k].idx] = res;
                for (int p = que[k].l; p <= que[k].r; ++p) --buc[a[p]];
                res = 0;
            } else break;
        }
        for (int r = inpart[que[i].l] * lenpart + lenpart - 1; k < j; ++k) {
            if (inpart[que[k].l] != inpart[que[k].r]) {
                while (r < que[k].r) add(a[++r]);
                int backup = res;
                for (int l = inpart[que[i].l] * lenpart + lenpart - 1; l >= que[k].l; --l) add(a[l]);
                ans[que[k].idx] = res;
                for (int l = inpart[que[i].l] * lenpart + lenpart - 1; l >= que[k].l; --l) --buc[a[l]];
                res = backup;
            }
        }
        memset(buc, 0, sizeof(buc));
        res = 0;
    }
}