bzoj 5301: [Cqoi2018]异或序列 (莫队算法)

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=5301

题面;

5301: [Cqoi2018]异或序列

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 476 Solved: 358
[Submit][Status][Discuss]

Description

已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ，给定查询参数 l、r ，问在 [l,r] 区间内，有多少连续子

序列满足异或和等于 k 。

也就是说，对于所有的 x，y (l≤x≤y≤r)，能够满足a[x]^a[x+1]^…^a[y]=k的x，y有多少组。

Input

输入文件第一行，为3个整数n，m，k。

第二行为空格分开的n个整数，即ai，a2,…．an。

接下来m行，每行两个整数lj，rj，表示一次查询。

1≤n，m≤105，O≤k，ai≤105，1≤lj≤rj≤n

Output

输出文件共m行，对应每个查询的计算结果。

Sample Input

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

Sample Output

4
2
1
2
1

思路：

因为区间[a,b]异或和可以由区间[1,a-1]和[1,b]异或得到，我们可以先预处理出前缀和，扔到莫队里维护，因为 a^b=k.那么 b = k^a，那么对a[i]来说，能与其异或成k的数就是 k^a[i]，加上这个数的数量，在莫队里维护下每个值的数量就好了

因为这里存的是前缀和，所以存询问的时候应该是 [l-1,r].

实现代码;

#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+;

int num[M],a[M],blo,k,ans,b[M];

struct node{

    int l,r,id;

    bool operator < (const node &cmp)const {

        if(l/blo == cmp.l/blo) return r < cmp.r;

        return l/blo < cmp.l/blo;

    }

}q[M];

void add(int x){

    ans += num[k^a[x]];

    num[a[x]]++;

}

void del(int x){

    ans -= num[k^a[x]];

     num[a[x]]--;

}

int main()

{

    int n,m;

    cin>>n>>m>>k;

    blo = sqrt(n);

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

        cin>>a[i];

        a[i] = a[i]^a[i-];

    }

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

        cin>>q[i].l>>q[i].r;

        q[i].l --;

        q[i].id = i;

    }

    sort(q+,q+m+);

    int l = ,r = ;

    ans = ;

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

        b[q[i].id] = ans;

    }

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

        cout<<b[i]<<endl;

    }

}

巴特西