跳转至

普通莫队

普通莫队算法用于离线处理区间查询问题。可以在 \(O(n\sqrt{m})\) 时间复杂度内将原问题转化为一个子问题：\(O(1)\) 向序列的开头或结尾插入或删除一个元素，\(O(\sqrt n)\) 以内求出序列答案。

得益于子问题良好的性质，莫队通常可以处理许多和值域有关的问题。比如桶数组相关、数颜色等等。

例题

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

题意

给定长度为 \(n\) 的颜色序列 \(a\)。有 \(m\) 次询问，每次询问给定区间 \([l,r]\)，问从区间中任意选择两个位置，颜色相等的概率是多少。以分数形式输出。

答案即

\[ \frac{\sum_{c\in col}{\binom{cnt[c]}{2}}}{\binom{r-l+1}{2}} \]

考虑 naive 的纯暴力：\(O(n)\) 统计区间颜色分布，时间复杂度为 \(O(nm)\)。

考虑另一种暴力：依次处理每个询问，每次查询都从上一个区间 \([l_{i-1},r_{i-1}]\) 暴力转移到 \([l_i,r_i]\)。即添加新区间中的新元素，删除旧区间中新区间不包含的旧元素。有多暴力呢？就是一个一个加，一个一个删。

显然这并没有对最劣时间复杂度起到任何有效的优化作用。考虑如何刻画转移的时间复杂度。我们将每一个查询 \([l,r]\) 都视为二维平面上的一个点 \((l,r)\)。这样，每次转移的时间复杂度就是两个对应点的曼哈顿距离。

这是 \(O(nm)\) 纯暴力（一种随机的、很劣的情况）

暴力1

然而可能的最优解应为

优化1

注意到两者之间的差异仅在于处理查询的顺序不同。莫队算法会通过某种排序，指定处理查询的顺序，从而将最劣时间复杂度算法限制在 \(O(n\sqrt m)\) 以内。

莫队采用分块的思路，将 \(n\) 分成一些长度相等的块；将所有查询按照 \(l\) 所在的块为第一关键字，\(r\) 的值为第二关键字排序，然后依次处理：

莫队

设块长为 \(b\)。考虑一个块内部的时间复杂度：\(x\) 每次最多变化 \(b\)，\(y\) 每次最多变化 \(n\)，但 \(y\) 均摊仍为 \(n\)。因此一个块的时间复杂度为 \(O(n+mb)\)，所有块的总时间复杂度为 \(O(\frac{n^2}{b}+mb)\)。应用基本不等式，平衡得 \(b=\frac{n}{\sqrt m}\)，此时总时间复杂度为 \(O(n\sqrt m)\)。

上界最优

事实上，对询问分块排序的时间复杂度上界已经达到了最优。假设 \(n,m\) 同阶且 \(n\) 是完全平方数。我们考虑形如 \(\big[a \sqrt n, b \sqrt n\big](1 \le a, b \le \sqrt n)\) 的区间，这样的区间一共有 \(n\) 个。此时最小曼哈顿生成树为 \(n\sqrt n\) 级别，和分块排序的时间复杂度相同。

注意 long long 和约分。可以给插入和删除写一个 update(int pos, int w) 函数，方便书写。

注意桶数组大小

莫队算法将会大量使用桶数组。注意有些题的值域范围并不是 \(n\)，桶数组不要开小了。

注意块长为 \(0\)

有时可以构造数据使得计算出的块长为 \(0\)，这样在后面的代码中就会出现除 \(0\) 错误。注意特判这种情况。

注意奇偶块排序比较函数的的严格弱序

sort() 使用的比较函数需要满足严格弱序，即满足以下三个性质：

  • 非自反性：cmp(a, a) -> false；
  • 反对称性：若 cmp(a, b) == true，则 cmp(b, a) = false；
  • ​传递性：若 cmp(a, b) == true，cmp(b, c) == true，则 cmp(a, c) -> true；

使用奇偶块排序时尤其需要注意这一点。比如

inline bool operator<(const Query& other) const {
    if(blo[l] ^ blo[other.l]) return blo[l] < blo[other.l];
    return (r < other.r) ^ (blo[l] & 1);
}

就不是严格弱序。因为当 r == other.r 且 blo[l] & 1 时，它不满足反对称性。因此我们应该这样写：

inline bool operator<(const Query& other) const {
    if(blo[l] ^ blo[other.l]) return blo[l] < blo[other.l];
    if(blo[l] & 1) return r < other.r;
    return r > other.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 5e4 + 10;

int blen, blo[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] ^ blo[other.l]) return blo[l] < blo[other.l];
        if(blo[l] & 1) return r < other.r;
        return r > other.r;
    }
} q[N];

ll c_ans;
int cl, cr;
ll cnt[N];

int n, m;
int a[N];
ll ans[N][2];

void update(int pos, int w) {
    ll &cur = cnt[a[pos]];
    c_ans -= cur * (cur - 1);
    c_ans += (cur + w) * (cur + w - 1);
    cur += w;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    blen = max(1, (int)(n / sqrt(m)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    sort(q + 1, q + 1 + m);

    cl = 1, cr = 0;
    for(int i = 1; i <= m; i++) {
        while(cr < q[i].r) update(++cr, 1);
        while(cl > q[i].l) update(--cl, 1);
        while(cr > q[i].r) update(cr--, -1);
        while(cl < q[i].l) update(cl++, -1);
        ans[q[i].id][0] = c_ans;
        ans[q[i].id][1] = 2 * max(1ll, ((ll)cr - cl + 1) * (cr - cl) / 2);
    }

    for(int i = 1; i <= m; i++) {
        if(ans[i][0] == 0) {
            cout << "0/1\n";
            continue;
        }
        ll g = __gcd(ans[i][0], ans[i][1]);
        ans[i][0] /= g;
        ans[i][1] /= g;
        cout << ans[i][0] << '/' << ans[i][1] << '\n';
    }

    return 0;
}

P3245 [HNOI2016] 大数

题意

给定一个长为 \(n\) 的数字串 \(s\) 和质数 \(p\)。有 \(m\) 次询问，每次询问给定区间 \([l,r]\)，询问 \(s[l,r]\) 有多少个子串对应的数字是 \(p\) 的倍数。

\(n,m\le 2\times 10^5,\ 2\le p\le 10^9\)

\(p=2\) 和 \(p=5\) 时特判。因为此时 \(10^k\) 不存在逆元，不能用前缀之差表示子串数字。

其余情况，先求出数组在模 \(p\) 意义下的前缀和数组。答案即区间中 \(s_i=s_j\) 的数对 \((i,j)\) 的数量。莫队维护桶即可。

代码 
  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
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N = 2e5 + 10;

inline ll qpow(ll a, int b, int p) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void lisanhua(ll *a, int n) {
    ll num[N], nn = n;
    for(int i = 1; i <= n; i++) num[i] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
    }
}

int blen, block[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(block[l] != block[other.l]) return block[l] < block[other.l];
        if(block[l] & 1) return r < other.r;
        return r > other.r;
    }
} q[N];

string buf;

int n, m, p;
ll a[N], s[N], s1[N], ans[N];

ll pw10[N];

int cl, cr;
ll c_ans;
int cnt[N];

inline void update(int pos, int w) {
    if(w > 0) {
        c_ans += cnt[s[pos]];
        ++cnt[s[pos]];
    } else {
        --cnt[s[pos]];
        c_ans -= cnt[s[pos]];
    }
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> p >> buf;
    n = buf.size();
    for(int i = 1; i <= n; i++) a[i] = buf[i - 1] - '0';

    cin >> m;
    blen = n / sqrt(m);
    for(int i = 1; i <= n; i++) block[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    if(p == 2 || p == 5) {
        for(int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + (a[i] % p == 0);
            s1[i] = s1[i - 1] + (a[i] % p == 0) * i;
        }
        for(int i = 1; i <= m; i++) {
            int l = q[i].l, r = q[i].r;
            cout << (s1[r] - s1[l - 1] + (1 - l) * (s[r] - s[l - 1])) << '\n';
        }
        return 0;
    }

    pw10[0] = 1;
    pw10[1] = 10;
    for(int i = 2; i <= n; i++) {
        pw10[i] = pw10[i - 1] * pw10[1] % p;
    }

    for(int i = n; i >= 1; i--) s[i] = (s[i + 1] + a[i] * pw10[n - i]) % p;
    lisanhua(s, n + 1);

    sort(q + 1, q + 1 + m);

    cl = 1, cr = 0;
    for(int i = 1; i <= m; i++) {
        ++q[i].r;
        while(q[i].r > cr) update(++cr, 1);
        while(q[i].l < cl) update(--cl, 1);
        while(q[i].r < cr) update(cr--, -1);
        while(q[i].l > cl) update(cl++, -1);
        ans[q[i].id] = c_ans;
    }

    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

P5355 [Ynoi Easy Round 2017] 由乃的玉米田

题意

给定一个长度为 \(n\) 的序列。有 \(m\) 次询问，每次询问给定 \(op,l,r,x\)，询问 \([l,r]\) 中是否存在 \(i,j\) 满足 \(a_i\otimes a_j=x\)；其中 \(\otimes\) 表示一种运算，\(op=1\) 时为减法，\(op=2\) 时为加法，\(op=3\) 时为乘法，\(op=4\) 时为除法。

考虑莫队维护一个桶和两个 bitset；加法、减法都用 bitset \(O(\frac{V}{\omega})\) 求出；乘法则枚举 \(x\) 的所有因数，时间 \(O(\sqrt V)\)。

考虑除法，如果我们暴力枚举 \(x\) 的倍数，在 \(x\) 很小时将产生接近 \(O(V)\) 的时间复杂度。考虑分治，对于 \(x> \sqrt V\)，直接暴力枚举 \(x\) 的倍数，时间 \(O(\sqrt V)\)；对于 \(x\le \sqrt V\)，我们可以开两个 \(n\times \sqrt V\) 的数组 pre1[i][j] 和 pre2[i][j]，分别表示 \(i\) 前面第一个 \(\frac{a_i}{j}\) 的下标，和 \(i\) 前面第一个 \(i\times j\) 的下标。这两个数组记录了所有极优的数对，我们只需要查找区间 \([l,r]\) 中是否存在这样的数对即可。

具体的，我们先对两个数组进行前缀最大值预处理，每次查询 \(l,r,x\) 时只需要判断 \(\max(pre1[r][x],pre2[r][x])\ge l\) 即可。预处理时间复杂度为 \(O(n\sqrt V)\)，查询 \(O(1)\)。

因为空间不够，我们将两个数组合并为一个数组。

总时间 \(O(m\frac{V}{\omega}+m\sqrt V+n\sqrt V)\) 。

代码 
  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
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include<iostream>
#include<bitset>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int V = 1e5;
const int L = 2e2;

int blen, blo[N];
struct Query {
    int op, l, r, x, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
        if(blo[l] & 1) return r < other.r;
        return r > other.r;
    }
} q[N];

int n, m;
int a[N];
bool ans[N];

namespace work_4 {
    int pre[N][L + 5];
    int lst[N];
    void work() {
        for(int i = 1; i <= n; i++) {
            lst[a[i]] = i;
            for(int j = 1; j <= L; j++) {
                if(a[i] % j == 0) pre[i][j] = lst[a[i] / j];
                if((ll)a[i] * j <= V) pre[i][j] = max(pre[i][j], lst[a[i] * j]);
                pre[i][j] = max(pre[i][j], pre[i - 1][j]);
            }
        }
        for(int i = 1; i <= m; i++) {
            if(q[i].op == 4 && q[i].x <= L) {
                ans[q[i].id] = pre[q[i].r][q[i].x] >= q[i].l;
            }
        }
    }
}

int c_l, c_r;
int cnt[N];
bitset<2 * N + 5> bs, rbs;

void update(int pos, int w) {
    cnt[a[pos]] += w;
    if(w > 0 && cnt[a[pos]] == 1) bs[a[pos]] = 1, rbs[2 * N - a[pos]] = 1;
    if(w < 0 && cnt[a[pos]] == 0) bs[a[pos]] = 0, rbs[2 * N - a[pos]] = 0;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> q[i].op >> q[i].l >> q[i].r >> q[i].x;
    for(int i = 1; i <= m; i++) q[i].id = i;

    blen = max(1, (int)(n / sqrt(m)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    sort(q + 1, q + 1 + m);

    work_4::work();

    c_l = 1, c_r = 0;
    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, x = q[i].x, id = q[i].id;
        if(q[i].op == 4 && q[i].x <= L) continue;
        while(l < c_l) update(--c_l, 1);
        while(c_r < r) update(++c_r, 1);
        while(c_l < l) update(c_l++, -1);
        while(r < c_r) update(c_r--, -1);
        switch(q[i].op) {
            case 1 : ans[id] = (bs & (bs >> x)).count(); break;
            case 2 : ans[id] = (bs & (rbs >> (2 * N - x))).count(); break;
            case 3 : {
                for(int j = 1; j * j <= x; j++) {
                    if(x % j) continue;
                    if(bs[j] && bs[x / j]) {
                        ans[id] = true;
                        break;
                    }
                }
            }; break;
            case 4 : {
                for(int j = x; j <= N; j += x) {
                    if(bs[j] && bs[j / x]) {
                        ans[id] = true;
                        break;
                    }
                }
            }; break;
        }
    }

    for(int i = 1; i <= m; i++) {
        cout << (ans[i] ? "yuno\n" : "yumi\n");
    }

    return 0;
}

 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
#include<iostream>
#include<bitset>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int L = 2e2;

int blen, blo[N];
struct Query {
    int op, l, r, x, id;
} q[N];

int n, m;
int a[N];
bool ans[N];

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> q[i].op >> q[i].l >> q[i].r >> q[i].x;

    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, x = q[i].x, id = q[i].id, op = q[i].op;
        try {
        for(int j = l; j <= r; j++) {
            for(int k = l; k <= r; k++) {
                if(op == 1 && a[j] - a[k] == x) throw 1;
                if(op == 2 && a[j] + a[k] == x) throw 1;
                if(op == 3 && a[j] * a[k] == x) throw 1;
                if(op == 4 && (a[j] % a[k] == 0 && a[j] / a[k] == x)) throw 1;
            }
        }
        } catch(int x) {
            ans[i] = 1;
        }
    }

    for(int i = 1; i <= m; i++) {
        cout << (ans[i] ? "yuno\n" : "yumi\n");
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include "testlib.h"
using namespace std;

int n = 10000;
int m = 10000;
int v = 100;

int main() {

    cout << n << ' ' << m << '\n';
    gen(n, 1, v);
    for(int i = 1; i <= m; i++) {
        cout << rng() % 4 + 1 << ' ';
        int l = rng() % n + 1, r = rng() % n + 1;
        if(l > r) swap(l, r);
        cout << l << ' ' << r << ' ' << rng() % v + 1 << '\n';
    }

    return 0;
}