题目描述
已知一个长度为n的整数数列a1,a2,...,an,给定查询参数l、r,问在al,al+1,...,ar区间内，有多少子序列满足异或和等于k。也就是说，对于所有的x,y (I ≤ x ≤ y ≤ r),能够满足ax⨁ax+1⨁...⨁ay=ka_x igoplus a_{x+1} igoplus ... igoplus a_y = kax⨁ax+1⨁...⨁ay=k的x,y有多少组。
输入格式
输入文件第一行，为3个整数n,m,k。
第二行为空格分开的n个整数,即a1,a2,..an。
接下来m行，每行两个整数lj,rj,表示一次查询。
输出格式
输出文件共m行，对应每个查询的计算结果。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,m,k,a[N],belong[N];
struct node{
int l,r,id;
}e[N];
inline bool cmp(node t1,node t2){
return (belong[t1.l]^belong[t2.l]) ? t1.l<t2.l : t1.r<t2.r;
}
int cnt[N],ans[N],sum;
inline void add(int x){
sum+=cnt[a[x]^k];
cnt[a[x]]++;
}
inline void del(int x){
cnt[a[x]]--;
sum-=cnt[a[x]^k];
}
signed main(){
cin>>n>>m>>k;
int size=sqrt(n);
int num=ceil((double)n/size);
for(int i=1;i<=num;i++)
for(int j=(i-1)*size+1;j<=i*size;j++)belong[j]=i;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]^=a[i-1];}
for(int i=1;i<=m;i++){scanf("%d%d",&e[i].l,&e[i].r);e[i].id=i;e[i].l--;}
sort(e+1,e+m+1,cmp);
int l=e[1].l,r=e[1].r;
for(int i=l;i<=r;i++)add(i);
for(int i=1;i<=m;i++){
while(l<e[i].l)del(l++);
while(l>e[i].l)add(--l);
while(r<e[i].r)add(++r);
while(r>e[i].r)del(r--);
ans[e[i].id]=sum;
}
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}