Codeforces617 E . XOR and Favorite Number(莫队算法)

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;
}
上一篇:[LeetCode] Maximum XOR of Two Numbers in an Array 数组中异或值最大的两个数字


下一篇:BZOJ4245 ONTAK2015 OR-XOR 【位运算+贪心】*