[Codeforces617E]XOR and Favorite Number（莫队）

2019-11-08 01:30:58

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

搞一下前缀和然后问题转化成[l-1,r]有多少对数xor为k 统计区间每一个数出现的个数，那么对于一个数i，有cnt[i^k]*cnt[i]对数xor为k 然后离线询问莫队修改就行了但是需要注意k=0的时候要特殊处理，因为0 xor i=i，所以计数的时候要变成cnt[i]*(cnt[i-1])/2

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 100005int n,m,k,block;int a[N],num[N],cnt[N*20];struct data{int id,l,r;LL ans;}q[N];LL ans;int cmp(data a,data b){ return num[a.l]<num[b.l]||(num[a.l]==num[b.l]&&num[a.r]<num[b.r]);}void modui(int l,int r,int f){ for (int i=l;i<=r;++i) { if (k) ans-=(LL)cnt[a[i]]*cnt[k^a[i]]; else ans-=(LL)cnt[a[i]]*(cnt[a[i]]-1)/2; cnt[a[i]]+=f; if (k) ans+=(LL)cnt[a[i]]*cnt[k^a[i]]; else ans+=(LL)cnt[a[i]]*(cnt[a[i]]-1)/2; }}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",&q[i].l,&q[i].r); --q[i].l;q[i].id=i; } block=sqrt(n); for (int i=1;i<=n;++i) num[i]=(i-1)/block+1; sort(q+1,q+m+1,cmp); ans=0LL; modui(q[1].l,q[1].r,1); q[q[1].id].ans=ans; for (int i=2;i<=m;++i) { if (q[i-1].l<q[i].l) modui(q[i-1].l,q[i].l-1,-1); else modui(q[i].l,q[i-1].l-1,1); if (q[i-1].r<q[i].r) modui(q[i-1].r+1,q[i].r,1); else modui(q[i].r+1,q[i-1].r,-1); q[q[i].id].ans=ans; } for (int i=1;i<=m;++i) PRintf("%I64d/n",q[i].ans);}

上一篇：sphinx 增量索引实现近实时更新

下一篇：QT Demo 之 window(5) window.qml