Problems and solutions to 5 kinds of “Mo’s Algorithm”

2021/01/19

Introduction:

This algorithm can solve some difficult data structure problems. Like this: Give an array \(a[]\) of size \(N\), we query \(Q\) times. Each time we want to get the mode number(the value that appears most often in a set of data) of subsequence \(a[l], a[l + 1] .. a[r].\)

  Maybe you want to solve it by segment tree or some other data structures. However, if you know the answer of \([l, middle], [middle + 1, r]\), it’s difficult to get the answer of \([l, r]\).Here is an offline algorithm which can solve this problem in \(O(N * sqrt(N) * log(N) + Q log Q)\). ——kAc

朴素莫队:SDOI2009《HH的项链》

题目描述:

HH 有一串由各种漂亮的贝壳组成的项链。

HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。

HH 不断地收集新的贝壳,因此他的项链变得越来越长。

有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?

这个问题很难回答,因为项链实在是太长了。

于是,他只好求助睿智的你,来解决这个问题。

输入格式:

第一行:一个整数 \(N\),表示项链的长度。

第二行:\(N\) 个整数,表示依次表示项链中贝壳的编号(编号为 \(0\) 到 \(1000000\) 之间的整数)。

第三行:一个整数 \(M\),表示 HH 询问的个数。

接下来 \(M\) 行:每行两个整数,\(L\) 和 \(R\),表示询问的区间。

输出格式:

\(M\) 行,每行一个整数,依次表示询问对应的答案。

数据范围:

\(1 ≤ N ≤ 50000\),

\(1 ≤ M ≤ 2×10^5\),

\(1 ≤ L ≤ R ≤ N\)

输入样例:

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出样例:

2
2
4

思路:

不同块的询问按照左端点升序,块内按照右端点升序。处理完一个块内所有询问的区间,才会处理下一个块。

分块区间长度的计算:假设块长为 \(a\),序列长为 \(n\),注意 \(a\) 是 \(int\) 类型。

左指针移动数量级 \(m × a\), \(m\) 是询问数量。

右指针移动数量级 \(\dfrac{n^2}{a}\),为了最优的分块复杂度,让左右指针移动的次数尽量相等,解出 \(a = \sqrt{\dfrac{n \times n}{m}}\)

对于左端点在同一个块内的询问,这些询问的右端点是升序的,所以每次处理一个块的时候,右指针扫描是递增的,也就是 \(O(N)\) 复杂度。而一共有大约 \(\sqrt{N}\) 个块,所以复杂度就是 \(O(N \times \sqrt{N})\)

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 50010, M = 200010, S = 1000010;

int n, m, len;
int w[N],  ans[M];

struct Quert {
    int id, l, r;
} q[M];

int cnt[S];  //哈希数组 每个数出现的次数

int get(int x) {
    return x / len;
}

bool cmp(const Quert& a, const Quert& b) {
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

void add(int x, int &res) {
    if (!cnt[x]) res ++;
    cnt[x] ++;
}

void del(int x, int &res) {
    cnt[x] --;
    if (!cnt[x]) res --;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    scanf("%d", &m);
    len = sqrt((double) n * n / m);

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

    //j是左边界指针 i是右边界指针 w[]下标都是从1开始
    //初始i=0,j=1是为了正确计算[1,1]的结果 i,j均从0开始也可以
    for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++) {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) add(w[++i], res);
        while (i > r) del(w[i--], res);
        while (j < l) del(w[j++], res);
        while (j > l) add(w[--j], res);
        ans[id] = res;
    }

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

 

之后再补充……这几天过年事比较多 2021.2.12