XOR and Favorite Number
| time limit per test: | 4 seconds |
|---|---|
| memory limit per test: | 256 megabytes |
| input: | standard input |
| output: | standard output |
Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, …, aj is equal to k.
Input
The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob’s favorite number respectively.
The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob’s array.
Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.
Output
Print m lines, answer the queries in the order they appear in the input.
Sample test(s)
Input
6 2 3
1 2 1 1 0 3
1 6
3 5
Output
7
0
Input
5 3 1
1 1 1 1 1
1 5
2 4
1 3
Output
9
4
4
Note
In the first sample the suitable pairs of i and j for the first query are: (1, 2), (1, 4), (1, 5), (2, 3), (3, 6), (5, 6), (6, 6). Not a single of these pairs is suitable for the second query.
In the second sample xor equals 1 for all subarrays of an odd length.
题意：有n个数和m次询问，每一询问会有一个L和R，表示所询问的区间，问在这个区间中有多少个连续的子区间的亦或和为k
思路：本题只有询问没有修改，所以比较适合离线处理，而莫队算法是离线处理一类区间不修改查询类问题的算法。就是如果你知道了[L,R]的答案。你可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的话。就可以使用莫队算法。，第一次接触莫队算法感觉是一种很优雅的暴力，莫队算法是莫涛发明的。先对序列分块。然后对于所有询问按照L所在块的大小排序。如果一样再按照R排序。然后按照排序后的顺序计算。为什么这样计算就可以降低复杂度呢。
一、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过2*n^0.5，不妨看作是n^0.5。由于有n个数，所以时间复杂度是n^1.5于是就变成了O(n^1.5)了。
对于这道题，假设我们现在有一个前缀异或和数组sum[]，现在我们要求区间[L,R]的异或的值，用sum数组表示就是sum[L-1]^sum[R]==K,或者说是K^sum[R]==sum[L-1]
详细见代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int Max = 1100000;
const int MAXM = 1<<22;
typedef struct node
{
int L ,R;
int Id;
}Point ;
Point a[Max];
LL sum[Max];
LL ans[Max];
int n,m;
LL k;
int L,R;
LL cnt[MAXM],ant;
bool cmp(Point b,Point c)//将区间分块排序
{
if(b.L/400==c.L/400)
{
return b.R<c.R;
}
else
{
return b.L<c.L;
}
}
void Dec(LL s) //将多算的数目去除
{
--cnt[s];
ant-=cnt[s^k];
}
void Inc(LL s)//将没有遍历的点对应的数目加上
{
ant += cnt[s^k];
cnt[s]++;
}
int main()
{
scanf("%d %d %lld",&n,&m,&k);
LL data;
for(int i=1;i<=n;i++) //
{
scanf("%lld",&sum[i]);
sum[i]^=sum[i-1];
}
for(int i=1;i<=m;i++)
{
scanf("%d %d",&a[i].L,&a[i].R);
a[i].Id = i;
a[i].L--;// 在这里提前处理
}
sort(a+1,a+m+1,cmp);
L=0,R=0,cnt[0]=1,ant=0;
for(int i=1;i<=m;i++)
{
while(R<a[i].R)
{
Inc(sum[++R]);
}
while(R>a[i].R)
{
Dec(sum[R--]);
}
while(L<a[i].L)
{
Dec(sum[L++]);
}
while(L>a[i].L)
{
Inc(sum[--L]);
}
ans[a[i].Id]=ant;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}