题意:

给定一个长度为n的整数数组,问有多少对互不重叠的非空区间,使得两个区间内的数的异或和为0。
N<1e3


题解:

如果直接暴力枚举两个区间的话 复杂度为O(n^4),显然不行。
观察一下数据范围,可以得到本题能够支持O(n^2)的做法,所以我们想怎么枚举一个区间能得到答案。
那么假设当前枚举的区间[i,j]两个区间中 右边的那一个,所以我们只需要知道 i 的左边有多少个区间的异或值和当前区间相等即可,我们用cnt数组表示出现次数。
这一部分我们可以动态维护:每次新加入一个数i时,他的贡献就为以他为右端点的异或值,那么我们每将i+1的时候就把以他为右端点的所有区间的异或值+1即可
复杂度O(n^2)


dai

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}

int _,n,a[maxn],cnt[maxn],pre[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) pre[i]=a[i]^pre[i-1];
    LL ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=1;j--) cnt[pre[i-1]^pre[j-1]]++;

        for(int j=i;j<=n;j++){
            ans+=cnt[pre[j]^pre[i-1]];
            //cout<<ans<<','<<i<<','<<j<<endl;
        }
    }
    printf("%lld\n",ans);
}