本文主要是介绍CodeForces 617E XOR and Favorite Number（莫队），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题意：给n个数和一个k，有很多次查询，每次查询有l,r,求[l,r]有多少个子区间的xor之和等于k
思路：首先，亦或运算存在一个性质，即a^a=0，a^0=a,那么a^b=c,则a^b^b=a=b^c（两边同时亦或b）,区间[l,r]的区间亦或和为a[l]^a[l+1]^...^a[r]=a[1]^...^a[l-1]^a[1]^...^a[r]=sum[r]^sum[r-1]，那么我们只需要预处理求出前缀就会大大减少运算时间。假设[l,r]的答案已知，那么[l,r+1]所增加的子区间包括[l,r+1]、[l+1,r+1]......[r+1,r+1]([l-1,r],[l+1,r],[l,r-1]同理),我们只要计算出这些区间的贡献即可，即sum[x](l<=x<=r)^sum[r+1]=k，可以转化为sum[r+1]^k=sum[x]，我们只需要预先存下前面的所有的前缀和即可，这些贡献等于cnt[sum[x]^k]。另外需要注意几个地方，区间的最大个数大约为n（n+1）/2(n=1e5)，需要long long存储；亦或值要会达到最大数的两倍；注意前缀和修改和改变答案的先后顺序；cnt[0]要初始化为1，可以这么认为，初始状态下，区间长度为0，区间亦或值为0区间个数为1，因为有可能加第一个数就会有答案；初始状态下，L=1，R=0，对左端点区间是修改的[L-1]。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
const int maxn = 1e6+5;
ll ans[10*maxn],res;
int a[maxn],cnt[2*maxn],n,m,k,bk;
struct Q{int l,r,id;
}q[maxn];bool cmp(Q a,Q b){///分块if(a.l/bk==b.l/bk) return a.r<b.r;return a.l/bk<b.l/bk;
}void add(int x){res+=cnt[a[x]^k];///注意先后顺序cnt[a[x]]++;
}void del(int x){cnt[a[x]]--;res-=cnt[a[x]^k];
}int main(){while(~scanf("%d%d%d",&n,&m,&k)){cnt[0]=1;///注意初始化bk=sqrt(n);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",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+m+1,cmp);int L=1,R=0;///注意初始化for(int i=1;i<=m;i++){while(L<q[i].l){del(L-1);///注意真实操作的位置L++;}while(L>q[i].l){///注意先后顺序L--;add(L-1);}while(R<q[i].r){R++;add(R);}while(R>q[i].r){del(R);R--;}ans[q[i].id]=res;}for(int i=1;i<=m;i++) cout<<ans[i]<<endl;}
}
这篇关于CodeForces 617E XOR and Favorite Number（莫队）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
