普通莫队

莫队算法简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。

莫队算法可以解决一类离线区间询问问题,基于双指针，分块，排序等思想，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队

莫队是处理离线区间询问的算法$O(n \sqrt n)$

假设$n = m$ ($m$为询问数，$n$为区间长度),对于任意一个区间$[l,r]$ 我们假设已经知道这个区间的$val$,我们可以通过拓展到$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$这四个区间，并且算出对应的$val$,那么我们的效率将会变得很高。

为了让我们的拓展次数变少,我们可以对每个询问进行排序，尽可能的让相近的区间同时查询。这就是莫队的一个很神奇的地方，采用了分块的思想，把区间分成一块一块的，这样我们的排序规则就是，先按照所属块的先后排序，然后同一块的再按照右端点排序，这样就大大降低了我们的时间复杂度。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void move(int pos, int sign) {
  // update nowAns
}
void solve() {
  BLOCK_SIZE = int(ceil(pow(n, 0.5)));
  sort(querys, querys + m);
  for (int i = 0; i < m; ++i) {
    const query &q = querys[i];
    while (l > q.l) move(--l, 1);
    while (r < q.r) move(++r, 1);
    while (l < q.l) move(l++, -1);
    while (r > q.r) move(r--, -1);
    ans[q.id] = nowAns;
  }
}

复杂度分析

莫队的复杂度证明比较复杂，这里贴上OI Wiki
莫队算法还有一个特点：当 n 不变时，m 越大，处理每次询问的平均转移代价就越小。一些其他的离线算法也具有同样的特点（如求 LCA 的 Tarjan 算法），但是莫队算法的平均转移代价随 m 的变化最明显。

排序优化

1
2
3
4
5
//假设块的大小为2
1 1
2 100
3 1
4 100

我们通过上面的数据可以发现，r指针的移动次数大概为300次，并且每一个区间的r，导致整体看起来像一个波浪，这里我们就要用到奇偶化排序。

什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数，一般情况下，这种优化能让程序快 30% 左右。

1
2
3
4
5
sort(query.begin() + 1, query.end(), [&](auto x, auto y) {
	if (K[x[0]] != K[y[0]]) return x[0] < y[0]; 
	if (K[x[0]] & 1) return x[1] < y[1]; 
	return x[1] > y[1]; 
});

例题

我们先拿最简单的应用，前缀和，众所周知，有很多方法都可以求前缀和，当然莫队也行。

前缀和

输入一个长度为 $n$ 的整数序列。

接下来再输入 $m$ 个询问，每个询问输入一对 $l, r$。

对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出格式

共 $m$ 行，每行输出一个询问的结果。

数据范围

$1 \le l \le r \le n$,
$1 \le n,m \le 100000$,
$-1000 \le 数列中元素的值 \le 1000$

输入样例：

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

输出样例：

3
6
10
对于每一个区间，我们考虑那四种情况:

  • 当左边需要增加一个位置，我们直接加上那个位置的值

  • 当左边需要减少一个位置，我们直接减少那个位置的值

  • 当右边需要增加一个位置，我们直接加上那个位置的值

  • 当右边需要减少一个位置，我们直接减少那个位置的值

    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
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <deque>
    #include <stack>
    #include <unordered_map>
    #include <unordered_set>
    #include <numeric>
    #include <iomanip>
    #define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define pb(e) push_back(e)
    #define all(x) (x).begin(), (x).end()
    #define allr(x) (x).rbegin(), (x).rend()
    #define endl '\n'

    using namespace std;
    using i64 = long long;
    using PII = pair<int,int>;
    const int INF = 0x3f3f3f3f;


    int main()
    {
    	int n,m;
    	cin >> n >> m;
    	vector<int> v(n + 1);
    	vector<array<int,3> > query(m+1);
    	for(int i=1;i<=n;++i) cin >> v[i];
    	for(int i=1;i<=m;++i)
    	{
    		int l,r;cin >> l >> r;
    		query[i] = {l,r,i};
    	}
    	int kn = n / min<int>(n,sqrt(m));
    	vector<int> K(n + 1);
    	for(int i=1;i<=n;++i) K[i] = (i - 1) / kn + 1;
    	sort(query.begin() + 1,query.end(),[&](auto x,auto y){
    		if(K[x[0]] != K[y[0]]) return x[0] < y[0];
    		if(K[x[0]] & 1) return x[1] < y[1];
    		return x[1] > y[1];
    	});

    	int l = 1,r = 0,val = 0;
    	vector<int> ans(m + 1);
    	for(int i=1;i<=m;++i)
    	{
    		auto &e = query[i];
    		int ql = e[0],qr = e[1],id = e[2];
    		auto add = [&](int x) -> void {
    			val += x;
    		};
    		auto sub = [&](int x) -> void {
    			val -= x;
    		};
    		while(l > ql) add(v[-- l]);
    		while(r < qr) add(v[++ r]);
    		while(l < ql) sub(v[l ++ ]);
    		while(r > qr) sub(v[r -- ]);
    		ans[id] = val;
    	}
    	for(int i=1;i<=m;++i) cout << ans[i] << endl;
    	return 0;
    }

小 Z 的袜子

然后是P1494 [国家集训队] 小 Z 的袜子 - 洛谷

其实莫队的写法基本上不同就只是在$add,sub$这两个函数之中。
这道题需要额外维护一个$cnt$数组，因为我们需要知道的是这个区间，相同颜色的袜子的数量，之后我们如何去算概率，首先我们考虑分母，一个完整的区间$[l,r]$,假如区间长度为$n$所有的组合次数为$C_n^2$,对应每一个分子，我们先考虑$add$加上颜色为$k$的袜子的情况，我们增加了一个$k$假如我们原来一共有$f$只，就是$C_f^2$现在我们需要更新了，因为多了一只，所以我的现在的情况即为$C_{f+1}^2$ ，然后我们再减去原来的。即为
$$
C_{f+1}^2 - C_f^2 = (f+1)*f / 2 - f * (f - 1) / 2
$$
$sub$同理,其实这个公式还可以简化，简化为$f$，但是为了清晰，下方代码并没有简化。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;

i64 gcd(i64 a,i64 b)
{
    return b ? gcd(b,a % b) : a;
}
int main()
{
    _fio
	int n,m;
	cin >> n >> m;
	vector<int> v(n + 1),cnt(n + 1);
	vector<array<int,3> > query(m+1);
	for(int i=1;i<=n;++i) cin >> v[i];
	for(int i=1;i<=m;++i)
	{
		int l,r;cin >> l >> r;
		query[i] = {l,r,i};
	}
	int kn = n / min<int>(n,sqrt(m));
	vector<int> K(n + 1);
	for(int i=1;i<=n;++i) K[i] = (i - 1) / kn + 1;
	sort(query.begin() + 1,query.end(),[&](auto x,auto y){
		if(K[x[0]] != K[y[0]]) return x[0] < y[0];
		if(K[x[0]] & 1) return x[1] < y[1];
		return x[1] > y[1];
	});

	int l = 1,r = 0;
    i64 val = 0;
	vector<i64> ans1(m + 1),ans2(m + 1);
	for(int i=1;i<=m;++i)
	{
		auto &e = query[i];
		int ql = e[0],qr = e[1],id = e[2];
        if(ql == qr)
        {
            ans1[id] = 0,ans2[id] = 1;
            continue;
        }
		auto add = [&](int x) -> void {
            val += (cnt[x] + 1)*cnt[x]/2 - cnt[x]*(cnt[x] - 1)/2;
            cnt[x] ++ ; 
		};
		auto sub = [&](int x) -> void {
            cnt[x] -- ; 
            val -= (cnt[x] + 1)*cnt[x]/2 - cnt[x]*(cnt[x] - 1)/2;
		};
		while(l > ql) add(v[-- l]);
		while(r < qr) add(v[++ r]);
		while(l < ql) sub(v[l ++ ]);
		while(r > qr) sub(v[r -- ]);
		ans1[id] = val;
        ans2[id] = (i64)(r - l + 1) * (r - l) / 2;
	}
	for(int i=1;i<=m;++i)
    {
        if(ans1[i] != 0)
        {
            i64 g = gcd(ans1[i],ans2[i]);
            ans1[i]/=g,ans2[i]/=g;
        }
        else
        {
            ans2[i] = 1;
        }
        cout << ans1[i] << "/" << ans2[i] << endl;
    }
	return 0;
}

XOR and Favorite Number

Problem - 617E - Codeforces

题面翻译

  • 给定一个长度为 $n$ 的序列 $a$，然后再给一个数字 $k$，再给出 $m$ 组询问，每组询问给出一个区间，求这个区间里面有多少个子区间的异或值为 $k$。
  • $1 \le n,m \le 10 ^ 5$，$0 \le k,a_i \le 10^6$，$1 \le l_i \le r_i \le n$。

我们要求$a_i \bigoplus a_{i+1} \bigoplus a_{i+2} \bigoplus … \bigoplus a_j$，可以通过前缀和，因为异或也满足类似前缀和的性质。
所以这个式子就变成了$(a_1 \bigoplus a_2 \bigoplus … \bigoplus a_{i-1}) \bigoplus (a_1 \bigoplus a_2 \bigoplus … \bigoplus a_j)$ ,如果用前缀和异或数组的话，这道题就变成了，有多少个数对$(i,j)$满足$a_i \bigoplus a_j = k$。之后直接莫队，因为$x \bigoplus y = z -> x \bigoplus z = y$ 所以就有我们每加入一个$x$,每一个对应的y都满足，所以把y的数量给加上,用$cnt$数组当做桶就行。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#define _fio                      \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);                   \
	cout.tie(0);
#define pb(e) push_back(e)
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define endl '\n'

using namespace std;
using i64 = long long;
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f;

int main()
{
	_fio
	int n, k, m;
	cin >> n >> m >> k;
	i64 kn = n / min<int>(n, sqrt(m));
	vector<int> v(n + 1), K(n + 1),cnt(2e6+10);
	vector<i64> ans(m + 1) ;
	vector<array<int, 3>> query(m + 1);
	for (int i = 1; i <= n; ++i)
		cin >> v[i], v[i] ^= v[i - 1], K[i] = (i - 1) / kn + 1;
	for (int i = 1; i <= m; ++i)
	{
		i64 l, r;
		cin >> l >> r;
		query[i] = {l - 1, r, i};//前缀和，直接l-1
	}
	sort(query.begin() + 1, query.end(), [&](auto x, auto y)
		 {
		if(K[x[0]] != K[y[0]]) return x[0] < y[0];
		if(K[x[0]] & 1) return x[1] < y[1];
		return x[1] > y[1]; 
		});
	int l = 1, r = 0;
	i64 val = 0;
	for (int i = 1; i <= m; ++i)
	{
		auto &e = query[i];
		int ql = e[0], qr = e[1], id = e[2];
		auto add = [&](int x) -> void
		{
			val += (i64)cnt[x ^ k];
			cnt[x]++;
		};
		auto sub = [&](int x) -> void
		{
			cnt[x]--;
			val -= (i64)cnt[x ^ k];
		};
		while (l > ql) add(v[--l]);
		while (r < qr) add(v[++r]);
		while (l < ql) sub(v[l++]);
		while (r > qr) sub(v[r--]);
		ans[id] = val;
	}
	for (int i = 1; i <= m; ++i)
		cout << ans[i] << endl;
	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
int main()
{
    int n, m;
    cin >> n >> m;
    i64 kn = n / min<int>(n, sqrt(m));
    vector<int> v(n + 1), K(n + 1);
    vector<i64> ans(m + 1);
    vector<array<int, 3>> query(m + 1);
    for (int i = 1; i <= n; ++i)
        cin >> v[i], K[i] = (i - 1) / kn + 1;
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        cin >> l >> r;
        query[i] = {l, r, i};
    }
    sort(query.begin() + 1, query.end(), [&](auto x, auto y)
        {
            if(K[x[0]] != K[y[0]]) return x[0] < y[0];
            if(K[x[0]] & 1) return x[1] < y[1];
            return x[1] > y[1];
        });
    int l = 1, r = 0, val = 0;
    for (int i = 1; i <= m; ++i)
    {
        auto &e = query[i];
        int ql = e[0], qr = e[1], id = e[2];
        auto add = [&](int x) -> void {
  
		};
        auto sub = [&](int x) -> void {
  
        };
        while (l > ql) add(v[--l]);
        while (r < qr) add(v[++r]);
        while (l < ql) sub(v[l++]);
        while (r > qr) sub(v[r--]);
        ans[id] = val;
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << endl;
    return 0;
}
算法
#algorithm #杂项
普通莫队
http://pikachuxpf.github.io/posts/a072cd53/
作者
Pikachu_fpx
发布于
2024年1月20日
许可协议