cf round340 div2 F（莫队）

旧城等待， 2022-06-13 02:00 277阅读 0赞

题目链接：**[传送门][Link 1]**

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 *a**i* of length *n*. Now he asks you to answer *m* queries. Each query is given by a pair *l**i* and *r**i* 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 *a**i*, *a**i* + 1, ..., *a**j* 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 *a**i* (0 ≤ *a**i* ≤ 1 000 000) — Bob's array.

Then *m* lines follow. The *i*\-th line contains integers *l**i* and *r**i* (1 ≤ *l**i* ≤ *r**i* ≤ *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

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.

**题目大意：**

给你一个序列a，和m次询问，和一个数k，每次询问你一个区间\[l,r\],问你在这个区间中有多少对i,j使得区间\[i,j\]的异或和等于k

**题目思路：**

首先考虑区间异或和，我们可用个数组pre\[i\] 表示前i个数的异或和，通过异或的性质我们可以求出i,j的异或和为pre\[j\]^pre\[i-1\]

有了这个我们还可以用个数组flag\[i\]表示当前这个 数i出现的次数，有了这些，如果我们知道了\[i,j\]的答案，那么我们可以在

O(1)的时间内求出\[i-1\]\[j\],\[i+1\]\[j\],\[i\]\[j-1\],\[i\]\[j+1\]内的值，所以有了这个我们就很好想到莫队，莫队的复杂度为m\*sqrt(n)

关于莫队可以看这个博客：[莫队详解][Link 2]

首先我们将区间分块，然后按快排序，然后对于我知道区间\[L,R\]的答案来求查询区间\[l,r\]的答案，这里可以做到

总复杂度为m\*sqrt(n)

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1<<20;
    struct node
    {
        int l,r,id;
    }q[maxn];
    int a[maxn],pos[maxn];
    int n,m,k,L=1,R=0;
    long long Ans=0,flag[maxn],ans[maxn];
    bool cmp(node a,node b)
    {
        if(pos[a.l]==pos[b.l])
            return a.r<b.r;
        else return pos[a.l]<pos[b.l];
    }
    void add(int x)
    {
    
        Ans+=flag[a[x]^k];
        flag[a[x]]++;
    }
    void del(int x)
    {
        flag[a[x]]--;
        Ans-=flag[a[x]^k];
    }
    int main()
    {
        scanf("%d%d%d",&n,&m,&k);
        int sz = sqrt(n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            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+1+m,cmp);
        flag[0] = 1;
        for(int i=1;i<=m;i++)
        {
    
            while(L<q[i].l)
            {
                del(L-1);
                L++;
            }
            while(L>q[i].l)
            {
                L--;
                add(L-1);
            }
            while(R<q[i].r)
            {
               R++;
               add(R);
            }
            while(R>q[i].r)
            {
                del(R);
                R--;
            }
            ans[q[i].id] = Ans;
        }
        for(int i=1;i<=m;i++)
            cout<<ans[i]<<endl;
    
        return 0;
    }

[Link 1]: http://codeforces.com/contest/617/problem/E
[Link 2]: http://blog.csdn.net/bossup/article/details/39236275