任意门：http://codeforces.com/problemset/problem/617/E

E. 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.

Examples

input

6 2 3
1 2 1 1 0 3
1 6
3 5

output

7
0

input

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 ）内有多少对（ i， j ）使得 ai ^ ai+1 ^ ... ^ aj = K;

解题思路：

这里的区间查询是离线的，可以用传说中的莫队算法（优雅而华丽的暴力算法）。

异或的题目有一个很巧妙的地方就是利用 a^b^a = b 这个性质。

这道题目我们也要预处理一下 sum(i) 前 i 个数的异或和，那么 ai ^ ai+1 ^ ... ^ aj = sum( i - 1) ^ sum( j ) 了。

接下来我们就可以按照查询的区间用莫队算法遍历一遍，同时记录当前区间某个前缀和的出现次数；

根据 sum( i - 1) ^ sum( j ) = K ，K ^ sum( i - 1 ) = sum( j ) || K ^ sum( j ) = sum( i - 1) ，由符合条件的前缀和次数来推出符合条件的（ i，j ）的个数啦。

Tip：

听了大神的课，这道题有两个坑：

1、答案的数据的数据范围是爆 int 的；

2、虽然是1e6 的 K，但异或的结果要大于 1e6 ；

AC code：

 #include <bits/stdc++.h>

 #define LL long long int

 using namespace std;

 const int MAXN = <<;

 struct node

 {

     int l, r, id;  //区间和查询编号

 }Q[MAXN];       //记录查询数据（离线）

 int pos[MAXN];  //记录分块

 LL ans[MAXN];   //记录答案

 LL flag[MAXN];  //维护前缀异或和出现的次数

 int a[MAXN];    //原本数据

 int L=, R;     //当前区间的左右结点

 LL res;         //储存当前区间的值

 int N, M, K;

 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];               //否则按照左结点分块排

 }

 void add(int x)

 {

     res+=flag[a[x]^K];

     flag[a[x]]++;

 }

 void del(int x)

 {

     flag[a[x]]--;

     res-=flag[a[x]^K];

 }

 int main()

 {

     scanf("%d%d%d", &N, &M, &K);

     int sz = sqrt(N);

     for(int i = ;  i <= N; i++){  //读入数据

         scanf("%d", &a[i]);

         a[i] = a[i]^a[i-];    //计算前缀异或和

         pos[i] = i/sz;         //分块

     }

     for(int i = ; i <= M; i++){    //读入查询

         scanf("%d%d", &Q[i].l, &Q[i].r);

         Q[i].id = i;

     }

     sort(Q+, Q++M, cmp);

     flag[] = ;

     for(int i = ;  i <= M; i++){

         while(L < Q[i].l){    //当前左结点比查询结点小

             del(L-);

             L++;

         }

         while(L > Q[i].l){    //当前左结点比查询左结点大

             L--;

             add(L-);

         }

         while(R < Q[i].r){    //当前右结点比查询右结点小

             R++;

             add(R);

         }

         while(R > Q[i].r){    //当前右节点比查询右节点大

             del(R);

             R--;

         }

         ans[Q[i].id] = res;

     }

     for(int i = ; i <= M; i++){

         printf("%lld\n", ans[i]);

     }

 }

秒客网

Codeforces Round #340 (Div. 2) E. XOR and Favorite Number 【莫队算法 + 异或和前缀和的巧妙】