做网站销售好不好,深圳市网站首页,网络营销公司名字,wordpress分享此文章[CQOI2018]异或序列
题意#xff1a;
给定1个整数K#xff0c;离线询问[l,r]中有多少子区间xor和K。
题解#xff1a;
异或有个重要的性质#xff1a;它的逆运算就是自身 我们维护该数列的前缀异或和a[x],表示1到x的区间异或和#xff0c;这样问题就变成了在区间[l-1,…[CQOI2018]异或序列
题意
给定1个整数K离线询问[l,r]中有多少子区间xor和K。
题解
异或有个重要的性质它的逆运算就是自身 我们维护该数列的前缀异或和a[x],表示1到x的区间异或和这样问题就变成了在区间[l-1,r]中有多少对数异或为k 然后一边莫队一边维护col[j]col[j]表示a[x]j的个数。 我们设y a[x]^k ----- a[x] ^ y k 这样每加入第x个位置此时区间内有多少y答案就加多少,anscol[y] 删去同理
代码
#includecmath
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
struct node{int l,h,r;
}q[100001];
int col[200001],n,m,ans,r; //col[i]表示当前区间有多少个数异或和为i
int a[100001],num[100001],k,blo,l;
inline bool cmp(node c,node d){if (c.l/blo!d.l/blo) return c.ld.l;if ((c.l/blo)1) return c.rd.r; return c.rd.r;
}
inline void add(int x){anscol[a[x]^k]; col[a[x]];}
inline void del(int x){col[a[x]]--; ans-col[k^a[x]];}
int main(){scanf(%d%d%d,n,m,k); blosqrt(n);for (int i1; in; i){scanf(%d,a[i]);//bl[i](i-1)/blo1;a[i]a[i-1]^a[i];}for (int i1; im; i){scanf(%d%d,q[i].l,q[i].r);q[i].hi; q[i].l--;}sort(q1,qm1,cmp);l1;for (int i1; im; i){while (lq[i].l) l--,add(l);while (lq[i].l) del(l),l;while (rq[i].r) r,add(r);while (rq[i].r) del(r),r--;num[q[i].h]ans;}for (int i1; im; i) printf(%d\n,num[i]);return 0;
}
