[莫队算法]异或序列
题目描述
已知一个长度为n的整数数列a1,a2,…,an，给定查询参数l、r，问在al,al+1,…,ar区间内，有多少子序列满足异或和等于k。也就是说，对于所有的x,y(l≤x≤y≤r)，满足ax⊕ax+1⊕⋯⊕ay=k的x,y有多少组。
输入
输入第一行为3个整数n,m,k。第二行为空格分开的n个整数，即a1,a2,…,an。接下来m行，每行两个整数lj,rj，代表一次查询。
输出
输出共m行，对应每个查询的计算结果。
样例输入
4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4
样例输出
4
2
1
2
1
提示
对于30%的数据，1≤n,m≤1000。
对于100%的数据，1≤n,m≤105,0≤k,ai≤105,1≤lj≤rj≤n。
思路：维护区间内每个数x出现频率(cnt[x])，以及区间内每个数x对答案的贡献(cnt[x^k]--因为x^(x^k)=k)，这两个信息可以在O(1)内由区间[L,R]转移到相邻区间；
AC代码:
#include <iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int n,m,k; int a[100010]; int cnt[100010]; int ans[100010]; int block; int ret; struct Query{ int l,r,id; }query[100010]; bool cmp(Query a,Query b){ if(a.l/block==b.l/block) return a.r<b.r; else return a.l/block<b.l/block; } void add(int pos){ cnt[a[pos]]++;ret+=cnt[a[pos]^k]; } void sub(int pos){ ret-=cnt[a[pos]^k];cnt[a[pos]]--; } int main() { scanf("%d%d%d",&n,&m,&k); 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",&query[i].l,&query[i].r),query[i].l--,query[i].id=i;//注意query[i].l要自减1 block=(int)sqrt(n); sort(query+1,query+1+m,cmp); int L=1,R=0; for(int i=1;i<=m;i++){ while(R<query[i].r) {R++;add(R);} while(R>query[i].r) {sub(R);R--;} while(L<query[i].l) {sub(L);L++;} while(L>query[i].l) {L--;add(L);} ans[query[i].id]=ret; } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }