题目描述
给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。输入描述:
第一行一个数n表示数组长度；
第二行n个整数表示数组；
1<=n<=1000,0<=数组元素<100000。
输出描述:
一行一个整数表示答案。示例1
输入
3
0 0 0
输出
5
说明
([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])
思路：
我们知道，两个区间的异或值为0的话，每个区间的异或值都是相等的。 所以我们O（n^2）预处理出区间的异或值，然后将其按照异或值从小到大排序，那么就将其分成了若干个段落，每个段落中的区间的异或值都是相等的， 那么将每个段落按照左端点从小到大排序，随便二分搞搞就行了。
Ac代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int L,R,val;
}b[1005000],c[10050000];
long long int ans;
int a[150000];
int cmp(node a,node b)
{
return a.val<b.val;
}
int cmp2(node a,node b)
{
return a.L<b.L;
}
void Slove(int ss,int ee)
{
int cnt=0;
for(int i=ss;i<=ee;i++)
{
cnt++;
c[cnt].L=b[i].L;
c[cnt].R=b[i].R;
c[cnt].val=b[i].val;
}
sort(c+1,c+1+cnt,cmp2);
for(int i=1;i<cnt;i++)
{
int l=i;
int r=cnt;
int pos=-1;
while(r-l>=0)
{
int mid=(l+r)/2;
if(c[mid].L>c[i].R)
{
pos=mid;
r=mid-1;
}
else l=mid+1;
}
if(pos==-1)continue;
else
{
ans+=cnt-pos+1;
}
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
ans=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=i;j<=n;j++)
{
sum^=a[j];
cnt++;
b[cnt].L=i;
b[cnt].R=j;
b[cnt].val=sum;
}
}
sort(b+1,b+1+cnt,cmp);
for(int i=1;i<=cnt;i++)
{
int ss=i;
int ee=i;
while(ee<cnt&&b[ee].val==b[ee+1].val)ee++;
Slove(ss,ee);
i=ee;
}
printf("%lld\n",ans);
}
}