传送门
突然发现自己没整理过异或的知识，正好借这个题整理一下。
关于异或
(1)异或就是在二进制下，两数各个位置上的数，相同为0，不同为1，所得到的数，比如说47，4的二进制是100,7的二进制是111，异或之后所得到的二进制数就是011=3，所以47=3。
(2)异或满足结合律与交换律，即ab=ba,(ab)c=a(bc)
(3)归零律:a^a=0
(4)a^0=a
(5)自反性:abb=a这个根据性质(3)(4)再加上结合律或者交换律很容易得出
解题思路
求区间异或和，可以先求出每个点的前缀异或和s[i]，那么从l到r的区间异或和就是s[r]^s[l-1] (原因根据以上性质很容易推出)。
然后可以先想暴力算法。对于每次询问l到r，可以用i枚举右端点，从l到r。用j枚举左端点，从l-1到i-1。用s[i]^s[j]如果满足条件就将ans++，单次询问复杂度达到了n方。
有了暴力做法，剩下的就是优化嘛。如果每次都去枚举这个区间的每个异或值，不如去用一个数组b记录下某个值，在这个区间出现的次数。然后每加入一个点所造成的影响就是，将k（最终要求得到的疑惑和）^s[i] (当前点的前缀异或和)在区间中出现的次数(也就是b[ka[i]])加到ans中去(可以这么做的原因是，我们要在前面区间中找到一个值x,使得s[i]x=k,也就是k^s[i]=x)。那要怎么维护这个b数组呢？？？莫队，\(N*\sqrt[2]{n}\)的复杂度似乎可过。那么问题就简单了，只要考虑莫队中怎么加入和删除就可以了。根据前面的推理，很容易得出加入一个元素s[i] (这里的s[i]还是表示前缀异或和)，就是将ans+b[k^s[i]]，然后将b[s[i]]++。
AC代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+100;
int b[N],a[N];
int n,m,k,block[N];
struct node
{
int l,r,ans,pos;
}q[N];
bool cmp(node x,node y)
{
if(block[x.l]!=block[y.l])
return block[x.l]<block[y.l];
return x.r<y.r;
}
int ans=0;
void ins(int x)
{
ans+=b[k^a[x]];
b[a[x]]++;
}
void del(int x)
{
ans-=b[k^a[x]];
b[a[x]]--;
}
bool cmp2(node x,node y)
{
return x.pos<y.pos;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int kk=sqrt(n);
for(int i=1;i<=n;++i)
{
block[i]=(i-1)/kk+1;
scanf("%d",&a[i]);
a[i]^=a[i-1];
}
for(int i=1;i<=m;++i)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].l--;
q[i].pos=i;
}
sort(q+1,q+m+1,cmp);
int ri=0,le=0;
b[0]=1;
for(int i=1;i<=m;++i)
{
int l=q[i].l,r=q[i].r;
while(le>l)
ins(--le);
while(ri<r)
ins(++ri);
while(ri>r)
del(ri--);
while(le<l)
del(le++);
q[i].ans=ans;
}
sort(q+1,q+m+1,cmp2);
for(int i=1;i<=m;++i)
printf("%d\n",q[i].ans);
return 0;
}