简要题意
给出一个三个正整数 \(n,m,k\) 和一个长度为 \(n\) 的序列 \(a\)。
有 \(m\) 个询问，每个询问给出一个区间 \([l,r]\)。求这个区间内有多少个子区间异或和等于 \(k\)。
允许离线。\(1 \leq n,m \leq 10^5,0 \leq a_i,k \leq 10^6\)。时间限制 \(4\text{s}\)。
思路
对于求一个区间的子区间约束计数问题，有几种经典思路。一种是扫描线（这个我不会），另一个是利用前缀和的特性，将原问题变成约束数对问题（经典例子 P5283 [十二省联考 2019] 异或粽子 这道题是可持久化 Trie+前缀和+堆）。
这道题可以使用第二个思路，因为异或可加又可减。
于是我们先对 \(a\) 求前缀异或和 \(b\)。然后原问题就变成了求 \([l-1,r]\) 中有多少个数对 \((u,v)\) 使得 \(b_u\otimes b_v=k\)。
由于这道题数据范围非常像 \(O(n\sqrt{n})\)，又可以离线。我们考虑使用普通莫队算法解决本问题。
具体来说，考虑插入一个 \(i\) 对答案的贡献，不难发现开个桶统计一下现在指针范围内 \(i\otimes k\) 有多少个（莫队经典思想），这就是贡献。
至于删除一个元素 \(i\)，我们可以减去 \(i\otimes k\) 的个数。
时间复杂度 \(O(n\log n+m\sqrt{m})\)，空间复杂度 \(O(n+m+k)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,m,k,a[N],blk,ans[N],tans,cnt[(int)(2e6+5)];
struct query{
int l,r,id;
bool operator<(const query &x) const {
return (l/blk)==(x.l/blk)?((r==x.r)?false:(((l/blk)&1)^(r<x.r))):(l<x.l);
}
} q[N];
inline void add(int x){tans+=cnt[x^k];cnt[x]++;}
inline void del(int x){cnt[x]--;tans-=cnt[x^k];}
signed main(){
cin>>n>>m>>k;
blk=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;
for(int i=1;i<=m;i++) q[i].l--,q[i].id=i;
sort(q+1,q+m+1);
for(int i=1,l=1,r=0;i<=m;i++){
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);
ans[q[i].id]=tans;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}