闲话：

• 在这篇题解中你会看到一些题解被 hack。

• 在这篇题解中你会知道 Del 和 Add 函数正确顺序和一些难理解东西的原理。

• 在这片题解中你会看见很多作者自己踩过的坑。

正文：

我们可以维护异或前缀和，那么 $l$ 到 $r$ 的异或和就为 $a_l-1 \bigoplus a_r$，问题就变成了询问区间 $[l-1 , r]$ 中，有多少对 $l$ 和 $r$ 满足 $a_{l-1} \bigoplus a_r = k$。

我们对于每个值，用莫队维护它出现的次数和在它之前满足与这个值异或起来为 $k$ 的数的个数，添加或删除点时答案对应加上或减去维护的个数即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e5+10,M=2e5+10;
int n,m,c;
int a[N];
struct Query { int l,r,id; } q[N];
int block;
int bel[N];
ll sum;
int tot[M];
ll ans[N];

bool cmp(Query a,Query b){
	return (bel[a.l]^bel[b.l]) ? bel[a.l]<bel[b.l] : ( (bel[a.l]&1) ? a.r<b.r : a.r>b.r ) ;
}

void Build(){
	block=pow(n,2.0/3.0);
	for(int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
}

void Add(int x) { sum+=tot[a[x]^c]; tot[a[x]]++; }

void Del(int x) { tot[a[x]]--; sum-=tot[a[x]^c]; }

int main(){
	scanf("%d%d%d",&n,&m,&c);
	Build();
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) a[i]^=a[i-1];
	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);
	tot[0]=1;
	int l=0,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l-1,qr=q[i].r,id=q[i].id;
		while(l<ql) Del(l++);
		while(l>ql) Add(--l);
		while(r<qr) Add(++r);
		while(r>qr) Del(r--);
		ans[id]=sum;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}

说几个坑点和不好理解的点吧 :

1. tot[0]=1 : 由于询问是对于区间 $[l-1,r]$ 的，所以询问范围为 $[0,n]$，又因为 $a_0=0$，所以要写上这句话，不然对于异或前缀和为 $k$ 的位置，显然有一个合法区间 $[1,x]$，其所对应的 $l$ 为 $0$，但由于 $tot_0=0$，没有统计答案。

2. l=0 : 由于询问范围为 $[0,n]$，自然 $l$ 初始值为 $0$ （这个 shaber 因为这个调了半天）。

3. ql=q[i].l-1 : 由于询问是对于区间 $[l-1,r]$。

4. void Add(int x) { sum+=tot[a[x]^c]; tot[a[x]]++; } : 由于询问是对于区间 $[l-1,r]$ 的，且 $l≤r$，所以在异或前缀和数组中这一定是两个位置，如果先写第二句话的话，当 $k=0$ 时，$sum$ 在统计答案时会会把当前位置算进当前位置的答案中加上，显然不合法，于是多算答案。

5. void Del(int x) { tot[a[x]]--; sum-=tot[a[x]^c]; } : 其实大致思路同上一条，由于询问是对于区间 $[l-1,r]$ 的，且 $l≤r$，所以在异或前缀和数组中这一定是两个位置，如果先写第二句话的话，当 $k=0$ 时，$sum$ 在统计答案时会把当前位置算进当前位置的答案中减去，显然不合法，于是少算答案。

6. tot[200010] 由于异或前缀和可能大于 $n$，最大值为 $2^{17}-1=131071$，故开这么大。

7. $l$ 和 $r$ 的加减与 Add 和 Del 的先后循序 : 删除是删除当前位置，故先 Del 再加减，添加是添加下一个位置，故先加减再 Add （这应该没人错吧 qwq )。

8. 由于是区间数量，记得开 long long。

对于上文第五条错误 $hack$ :

2

4 1 0
0 1 0 1
2 4

正确输出 :

2

错误输出 :

1

对于上文第八条错误 hack : (叉了6篇)

2

100000 1 0
(100000个0)
1 100000

正确输出 :

5000050000

错误输出 :

705082704

数组越界应该不用我说怎么卡了吧 qwq （其实我也不会

有错误请及时回复或私信我，谢谢啦！

写在最后：希望被 hack 的题解不要只改了代码，不写明原理，只是说 “脑抽了” 之类的话。

Upd : 11.22 改了评论区指出的错误

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+10;
int n,m,c;
int B; 
int a[N];
struct Query {
	int l,r,id; 
	bool operator <(const Query &A){
		return l/B!=A.l/B?l<A.l:((l/B)&1?r<A.r:r>A.r);
	}
} q[N];//记录问题 
int sum;
int tot[N];
int ans[N];
void Add(int x){//添加影响 
	sum+=tot[x^c];//这是跟数字x相异或能够为c的 
	tot[x]++;
}
void Del(int x){//消除影响
	tot[x]--;
	sum-=tot[x^c];//这是跟数字x相异或能够为c的
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>c;
	B=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) a[i]^=a[i-1];
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+m);
	for(int i=1,l=0,r=-1;i<=m;i++){//经典莫队板子 
		int ql=q[i].l-1,qr=q[i].r,id=q[i].id;//注意范围 
		while(l<ql) Del(a[l++]);
		while(l>ql) Add(a[--l]);
		while(r<qr) Add(a[++r]);
		while(r>qr) Del(a[r--]);
		ans[id]=sum;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}

拿莫队模板改的，忘记改数组名了，调了十分钟。。。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,k,b,sum,a[N];
int Xor[N],cnt[N],ans[N];
struct nd{int l,r,id;}q[N];
bool cmp(nd n1,nd n2)
{
	if(n1.l/b!=n2.l/b)return n1.l<n2.l;
	if((n1.l/b)&1)return n1.r<n2.r;
	return n1.r>n2.r;
}
void add(int x)
{
	sum+=cnt[x^k];
	cnt[x]++;
}
void del(int x)
{
	cnt[x]--;
	sum-=cnt[x^k];
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);b=sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),Xor[i]=Xor[i-1]^a[i];
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=0,r=-1;i<=m;i++)
	{
		while(l<q[i].l-1)del(Xor[l++]);
		while(l>q[i].l-1)add(Xor[--l]);
		while(r<q[i].r)add(Xor[++r]);
		while(r>q[i].r)del(Xor[r--]);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

初尝受挫

一开始想着用前缀和来做，但没想到可以用莫队来维护，就打了一个30分的暴力：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,a[100010];
ll solve(ll l,ll r)
{
	ll ans=0;
	for(ll i=l;i<=r;i++)
	{
		ll s=a[i];
		for(ll j=i+1;j<=r;j++)
		{
			if(s==k)ans++;
			s^=a[j];
		}
		if(s==k)ans++;
	}
	return ans;
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	while(m--)
	{
		ll l,r;scanf("%lld%lld",&l,&r);
		printf("%lld\n",solve(l,r));
	}
	return 0;
}

题解引导

现在想想，莫队也不难做，前缀和思想就是将l到r的异或和转化为$(a_l-1)$^$a_r$，然后对于每个区间的$l$维护它出现的次数和在它之前满足与这个值异或起来为$k$的数的个数，添加或删除点时答案对应加上或减去维护的个数即可......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10;
ll n,m,k,a[N];
struct node{ll l,r,id;}q[N];
ll f,bel[N],sum,tot[140000],ans[N];
inline bool cmp(node a,node b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]<bel[b.l]:((bel[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline void build()
{
	f=pow(n,2.0/3.0);
	for(ll i=1;i<=n;i++)bel[i]=(i-1)/f+1;
}
inline void add(ll x){sum+=tot[a[x]^k];tot[a[x]]++;}
inline void del(ll x){tot[a[x]]--;sum-=tot[a[x]^k];}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	build();
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(ll i=1;i<=n;i++)a[i]^=a[i-1];
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	tot[0]=1;
	ll l=0,r=0;
	for(ll i=1;i<=m;i++)
	{
		ll ql=q[i].l-1,qr=q[i].r,id=q[i].id;
		while(l<ql)del(l++);
		while(l>ql)add(--l);
		while(r<qr)add(++r);
		while(r>qr)del(r--);
		ans[id]=sum;
	}
	for(ll i=1;i<=m;i++)printf("%lld\n",ans[i]);
	return 0;
}

.........................................................................................................................................................................