本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
描述
对于给定的n和m以及a1,...,ana1,...,an，请你计算：
s=∑ni=1max1≤j≤min{m,n−i+1}{ai⊕ai+1⊕...⊕ai+j−1} }
s=∑i=1nmax1≤j≤min{m,n−i+1}{ai⊕ai+1⊕...⊕ai+j−1}
格式
输入格式
第1行为空格分隔的n和m。
第2行为空格分隔的$${a1,...,ana1,...,an}$$。
输出格式
一个数字，为计算结果s（只保留低31位即可）。
限制
1≤m≤n≤5×1051≤m≤n≤5×105
∀i∈[1,n],1≤ai≤231−1∀i∈[1,n],1≤ai≤231−1
时间
前三个测试点 1s
剩下的 2s
空间
384MiB
正解：trie+贪心
解题报告：
异或类的题目，显然拆成一位一位的会好做多了。记得以前我出的题目里面出过一道类似的...
按每一位是1或0建一棵trie树，然后因为每次的查询有范围限制，所以可以看做是在trie上动态插入元素或者删除元素，只需要维护一个每个结点的经过次数，就可以处理这个问题。
插入就很简单了。查询呢？对于sum[i-1]（sum数组为前缀异或和）在trie上查询，每一位尽可能选择不同，如果不存在不同的就只能选择这一位选择相同，那么就没有贡献。如果可以不同就继续顺着trie树上走，并加入贡献。
插入和删除的话就把经过的结点经过次数++或者--。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (<<);
const int MAXN = ;
int n,m,a[MAXN],sum[MAXN];
int tr[MAXN][],ci[MAXN],cnt;
LL ans; inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
}
inline void insert(int x){
int u=,num; ci[u]++;
for(int i=;i>=;i--) {
num=(x>>i)&; if(!tr[u][num]) tr[u][num]=++cnt;
u=tr[u][num]; ci[u]++;
}
}
inline void del(int x){ int u=,num; ci[u]--; for(int i=;i>=;i--) { num=(x>>i)&; u=tr[u][num]; ci[u]--; } }
inline void query(int x){
int u=,num; int now_ans=;
for(int i=;i>=;i--) {
num=(x>>i)&;
if(!tr[u][num^] || ci[tr[u][num^]]==) u=tr[u][num];
else u=tr[u][num^],now_ans+=(<<i);
}
ans+=now_ans;
} inline void work(){
n=getint(); m=getint(); for(int i=;i<=n;i++) a[i]=getint(),sum[i]=sum[i-]^a[i]; cnt=;
int nowl=; while(nowl<m) insert(sum[nowl]),nowl++;
for(int i=;i<=n;i++) {
if(nowl<=n) insert(sum[nowl]),nowl++;
query(sum[i-]);
del(sum[i]);
}
LL MOD=(1LL<<); ans%=MOD;
printf("%lld",ans);
} int main()
{
work();
return ;
}