Xorto（xor前缀和）

题目：

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

做法：

首先预处理出 $prefix[]$ 数组， $prefix[i]$ 表示 $[1,i]$ 这个区间元素的 $xor$ 和。
这样我们就可以 $O(1)$ 得到任意区间的 $xor$ 和。[l,r]区间的xor和 = prefix[r]^prefix[l-1]。
设选出的互不重叠区间对为A、B，且A在B左侧。
我们枚举B的左端点x。此时我我们已经记录下了所有右端点小于x的区间，也就是合法的A已经全部记录下来了。则对于每个x，我们再枚举右端点y，看有几个A能匹配就行了。枚举完x后，将右端点为x的区间记录一下，因为下一次我们将枚举x+1。以x为右端点的区间可以作为合法的A。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int a[1010], prefix[1010], mp[N];
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        prefix[i] = prefix[i-1]^a[i];
    }    
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = i; j <= n; ++j){
            int x = prefix[j]^prefix[i-1];
            ans += mp[x];
        }
        for (int j = 1; j <= i; ++j){
            int x = prefix[i]^prefix[j-1];
            mp[x]++;
        }
    }
    cout << ans << endl;
    return 0;
}