莫队算法

ACM

莫队算法只能离线的进行查询，不能在线的进行修改。通过改变查询的顺序，从而降低算法的时间复杂度。

题目

XOR and Favorite Number

题意

  • 给定n个数，然后给出m个询问，每一个询问为[L, R]区间内的询问。问区间内有多少对数，使得它们连续的亦或为k.

题解

  1. 我们可以预处理亦或的前缀和pre[]，那么当求[l, r]区间内的亦或和时，直接用pre[l-1]^pre[r]来求一个区间的亦或和。
  2. 用莫队的思想，对查询进行排序，从而降低算法的时间复杂度。\(O(n\sqrt{n})\)

代码

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 <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
typedef long long LL;
LL a[maxn];//记录亦或的前缀和
struct Node{
    int l ,r, id;
}Q[maxn];
int pos[maxn];//分块的编号
LL ans[maxn];
LL flag[maxn];//每一个前缀出现的次数
bool cmp(Node a, Node b){
    if(pos[a.l] == pos[b.l]){
        return a.r<b.r;
    }
    return pos[a.l] < pos[b.l];
}
int n, m, k;
int L = 1, R = 0;
LL Ans = 0;
void del(int index){
    flag[a[index]]--;//a[index]可能等于a[index]^k
    Ans -= flag[a[index]^k];
}
void add(int index){
    Ans += flag[a[index]^k];
    flag[a[index]]++;
}
int main()
{
    while(~scanf("%d%d%d", &n, &m, &k)){
        L = 1, R = 0, Ans = 0;
        memset(flag, 0, sizeof(flag));
        a[0] = 0;
        int sz = sqrt(n);
        for(int i=1; i<=n; i++){
            scanf("%d", &a[i]);
            a[i] ^= a[i-1];
            pos[i] = i/sz;
        }
        for(int i=1; i<=m; i++){
            scanf("%d%d", &Q[i].l, &Q[i].r);
            Q[i].id = i;
        }
        sort(Q+1, Q+m+1, cmp);
        flag[0] = 1;
        for(int i=1; i<=m; i++){
            while(Q[i].l>L){
                del(L-1);
                L++;
            }
            while(Q[i].l<L){
                L--;
                add(L-1);
            }
            while(Q[i].r>R){
                R++;
                add(R);
            }
            while(Q[i].r<R){
                del(R);
                R--;
            }
            ans[Q[i].id] = Ans;
        }
        for(int i=1; i<=m; i++){
            printf("%I64d\n", ans[i]);
        }
    }
    return 0;
}

未解决的问题

本文标题:莫队算法

文章作者:Babydragon

发布时间:2018-02-19, 18:03:37

最后更新:2018-03-23, 13:33:20

原始链接:http://baolintian.github.io/2018/02/19/莫队算法/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目
  2. 2. 题意
  3. 3. 题解
  4. 4. 代码
  5. 5. 未解决的问题
{{ live2d() }}