CodeForces 617E XOR and Favorite Number

莫队算法。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=+;
int a[maxn],pre[maxn];
long long cnt[*maxn];
int pos[maxn];
int n,m,k;
long long ans[maxn];
long long Ans;
int L,R;
struct X
{
int l,r,id;
}s[maxn]; bool cmp(const X&a,const X&b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;
return a.l<b.l;
} int main()
{
scanf("%d%d%d",&n,&m,&k); int sz=sqrt(n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
pre[i]=(pre[i-]^a[i]);
pos[i]=i/sz;
} for(int i=;i<=m;i++)
{
scanf("%d%d",&s[i].l,&s[i].r);
s[i].id=i;
} sort(s+,s++m,cmp);
Ans=; cnt[pre[s[].l-]]++; for(int i=s[].l;i<=s[].r;i++)
{
Ans=Ans+cnt[pre[i]^k];
cnt[pre[i]]++;
} L=s[].l; R=s[].r;
ans[s[].id]=Ans; for(int i=;i<=m;i++)
{
while(L<s[i].l)
{
cnt[pre[L-]]--;
Ans=Ans-cnt[pre[L-]^k];
L++;
} while(L>s[i].l)
{
L--;
Ans=Ans+cnt[pre[L-]^k];
cnt[pre[L-]]++;
} while(R<s[i].r)
{
R++;
Ans=Ans+cnt[pre[R]^k];
cnt[pre[R]]++;
} while(R>s[i].r)
{
cnt[pre[R]]--;
Ans=Ans-cnt[pre[R]^k];
R--;
}
ans[s[i].id]=Ans;
} for(int i=;i<=m;i++)
printf("%lld\n",ans[i]); return ;
}
上一篇:MYSQL数据库45道练习题


下一篇:quartz定时任务的简单使用