莫队算法

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

题目

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;
}

未解决的问题

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