Codeforces617E-XOR and Favorite Number-莫队算法模板

（有任何问题欢迎留言或私聊

题意：传送门

 翻译过来大概是，给你一个区间，区间内应该有一些数的异或和等于k，求异或和等于k的方案数。

flag[i]保存的是区间内异或和为 i 的方案数
我们已知区间[L,R]的情况，从区间[L,R]可以O(1)得到[L+1,R],[L-1,R],[L,R-1],[L,R+1]的情况
ans数组保存的是每次询问的答案
然后处理出异或前缀和数组ar[N]
[L,R]区间的异或和就是ar[R]^ar[L-1]

初始化
flag[0]=1;因为区间内什么都不选，异或值就是0这是一种方案。
已知区间：int L,R;
重点：将询问的区间排个序，然后玄学使得总时间复杂度降低。O(n^1.5);

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1<<20;
int belong[N];
LL flag[N],ans[N],ar[N];
int n,m,k;
int L=1,R=0;
LL Ans=0;
struct lp{
    int l,r,id; 
}cw[N];
bool cmp(const lp &a,const lp &b){
    if(belong[a.l]==belong[b.l]){
        return a.r<b.r;
    }
    return belong[a.l]<belong[b.l];
}
void add(int x){
    Ans+=flag[ar[x]^k];
    flag[ar[x]]++;
}
void del(int x){
    flag[ar[x]]--;
    Ans-=flag[ar[x]^k];
}
int main(int argc, char const *argv[]){
    while(~scanf("%d%d%d",&n,&m,&k)){
        ar[0]=0,L=1,R=0,Ans=0;
        memset(flag,0,sizeof(flag));
        int sz=sqrt(n);
        for(int i=1;i<=n;++i){
            scanf("%lld",&ar[i]);
            ar[i]=ar[i]^ar[i-1];
            belong[i]=i/sz;
        }
        for(int i=0;i<m;++i){
            scanf("%d%d",&cw[i].l,&cw[i].r);
            cw[i].id=i;
        }
        sort(cw,cw+m,cmp);
        flag[0]=1;
        for(int i=0;i<m;++i){
            while(L<cw[i].l){
                del(L-1);
                L++;
            }
            while(L>cw[i].l){
                L--;
                add(L-1);
            }
            while(R<cw[i].r){
                add(++R);
            }
            while(R>cw[i].r){
                del(R--);
            }
            ans[cw[i].id]=Ans;
        }
        for(int i=0;i<m;++i){
            printf("%lld\n",ans[i]);
        }
    }