题目链接

---

题意：求给定询问区间[L,R]问有多少连续区间异或值等k，多次询问可以离线。

a[i]^a[i+1]^a[i+2]^a[n]=(a[1]^a[2]^a[3]^...^a[i-1])^(a[1]^a[2]^a[3]^...^a[n-1]^a[n])

所以可以转化为前缀异或和，问题就变为有多少对a[i]^a[j]=k;所以莫队算法的操作就明了。

因为a^b=k则a^k=b，每次记录cnt更新的数出现的次数，每次ans加上或者减去cnt[该数^k]即可

注意点：对于任意询问(x,y)转化为前缀就是  a[x-1]^a[y]，所以实际询问(x-1,y)

还有就是cnt[0]要赋值为1。

具体看代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2]={0,1,0,-1,1,0,-1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int cnt[1<<20];
int n,m,k,u;
ll ans,res[maxn];
struct node
{int l,r,id;
}s[maxn];
bool cmp(node x,node y){return x.l/u!=y.l/u?x.l<y.l:x.r<y.r;}
void add(int x)//先更新答案，再更新数组
{ans+=cnt[a[x]^k];//a^b=k 则 a^k=bcnt[a[x]]++;
}
void del(int x)//先更新数组，再更新答案
{cnt[a[x]]--;ans-=cnt[a[x]^k];
}
int main()
{int l,r;scanf("%d %d %d",&n,&m,&k);u=sqrt(n);cnt[0]=1;//初始条件for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=a[i]^a[i-1];for(int i=1;i<=m;i++) scanf("%d %d",&s[i].l,&s[i].r),s[i].id=i;sort(s+1,s+1+m,cmp);l=0,r=0,ans=0;//l从0开始，因为比较 r-(l-1)for(int i=1;i<=m;i++){while(l+1>s[i].l) add(--l);while(l+1<s[i].l) del(l++);while(r<s[i].r) add(++r);while(r>s[i].r) del(r--);res[s[i].id]=ans;}for(int i=1;i<=m;i++)printf("%lld\n",res[i]);return 0;
}

 

总结

以上是生活随笔为你收集整理的XOR and Favorite Number CF340E 莫队算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。