【莫队算法】[CodeForces - 617E/Round #340]XOR and Favorite Number

题目

分析：求异或的前缀和后用莫队算法即可。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 100000
#define MAXM 100000
#define MAXK 1000000
using namespace std;
int block[MAXN+],n,m,a[MAXN+],k,cnt[MAXK*2+],sum[MAXN+];
long long ans[MAXM+];
void Read(int &x){
    char c;
    while(c=getchar(),c!=EOF)
        if(c>='0'&&c<='9'){
            x=c-'0';
            while(c=getchar(),c>='0'&&c<='9')
                x=x*10+c-'0';
            ungetc(c,stdin);
            return;
        }
}
struct node{
    int l,r,i;
    bool operator<(const node& x)const{
        if(block[l]==block[x.l])
            return r<x.r;
        return block[l]<block[x.l];
    }
}q[MAXM+10];
void init(){
    Read(n),Read(m),Read(k);
    int i,t=sqrt(n+.);
    for(i=;i<=n;i++){
        Read(a[i]),sum[i]=sum[i-]^a[i];
        block[i]=(i+t-)/t;
    }
    for(i=;i<=m;i++){
        Read(q[i].l),Read(q[i].r);
        q[i].l--;
        q[i].i=i;
    }
    sort(q+,q+m+);
}
void solve(){
    int i,l=,r=-;
    long long ansn=;
    for(i=;i<=m;i++){
        while(r<q[i].r)
            ansn+=cnt[sum[++r]^k],cnt[sum[r]]++;
        while(r>q[i].r)
            cnt[sum[r]]--,ansn-=cnt[sum[r--]^k];
        while(l<q[i].l)
            cnt[sum[l]]--,ansn-=cnt[sum[l++]^k];
        while(l>q[i].l)
            ansn+=cnt[sum[--l]^k],cnt[sum[l]]++;
        ans[q[i].i]=ansn;
    }
}
void print(){
    for(int i=;i<=m;i++)
        printf("%I64d\n",ans[i]);
}
int main()
{
    init();
    solve();
    print();
}