【传送门：BZOJ5301】
简要题意：
给出长度为n的序列，给出m个询问，并给出k，每个询问输入l,r
每个询问输出l到r的序列中的所有子串中的异或和为k的子串数量
题解：
莫队
异或，真是个神东西
首先异或和满足前缀，也就是说设sum[i]为a[1]^a[2]^...^a[i]，那么a[i]^a[i+1]^...^a[j]=sum[j]^sum[i-1]
而且异或不仅满足交换律，而且对于a^b=c时，a^c=b，b^c=a这两个式子同样成立
那么就好做了，假设当前i到j这个子串的异或和为k，就说明sum[j]^sum[i-1]=k，也就是sum[i-1]^k=sum[j]，sum[j]^k=sum[i-1]
然后在区间转移的时候，设cnt[i]为当前区间值为i的前缀有多少个，然后对于增加序列长度的操作，假设新加的位置为r+1，我们先将cnt[sum[r+1]]++，然后求出ans+=cnt[sum[r+1]^k]，左边扩展也是如此，不过注意，向左扩展时，对ans的更新是用sum[l-1]的，因为是sum[j]与sum[i-1]可以满足前缀
而且向右扩展的时候，如果sum[r+1]^k=sum[l-1]的话，ans++，因为我们更新的时候没有计算[l...r+1]区间的影响，所以要维护一下
而对于区间缩小的情况，就ans先减，再更新cnt，因为要先消除贡献再减cnt，其它步骤类似就好了
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; typedef long long LL; struct question { int l,r,id;LL d; }q[110000]; int belong[110000],block; bool cmp1(question n1,question n2) { if(belong[n1.l]==belong[n2.l]) return n1.r<n2.r; else return belong[n1.l]<belong[n2.l]; } bool cmp2(question n1,question n2) { return n1.id<n2.id; } LL ans; int sum[110000]; LL cnt[110000]; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { int d; scanf("%d",&d); sum[i]=sum[i-1]^d; } block=int(sqrt(n)); for(int i=1;i<=n;i++) belong[i]=(i-1)/block+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+m+1,cmp1); memset(cnt,0,sizeof(cnt)); int l=1,r=0;ans=0; for(int i=1;i<=m;i++) { while(r<q[i].r) { r++; cnt[sum[r]]++; ans+=cnt[sum[r]^k]; if((sum[r]^k)==sum[l-1]) ans++; } while(r>q[i].r) { ans-=cnt[sum[r]^k]; cnt[sum[r]]--; if((sum[r]^k)==sum[l-1]) ans--; r--; } while(l<q[i].l) { ans-=cnt[sum[l-1]^k]; cnt[sum[l]]--; l++; } while(l>q[i].l) { l--; cnt[sum[l]]++; ans+=cnt[sum[l-1]^k]; } q[i].d=ans; } sort(q+1,q+m+1,cmp2); for(int i=1;i<=m;i++) printf("%lld ",q[i].d); return 0; }