【每日一题】Xorto

题目大意

存在多少对不重叠非空的区间，异或值相同。

解题思路

因为对于异或来说，前缀和性质依然适用， 预处理从1到i的异或和
这样我们可以求到
我们枚举左区间的右端点 ，求得以i为右端点的全部区间异或值。
并且枚举以 为左端点的所有区间是否有和前面异或值相同的，如果相同更新答案。

时间复杂度

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int N = 1e3 + 7;
const int M = 1e5 + 7;

ll sum[N], mp[M << 1];
ll ans;

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        sum[i] = sum[i - 1] ^ x; //处理前缀和  这样[l,r]异或值为sum[r]^sum[l-1]
    }
    for (int i = 1; i <= n; ++i) { //枚举右端点
        for (int j = 1; j <= i; ++j)
            ++mp[sum[i] ^ sum[j - 1]];
        for (int j = i + 1; j <= n; ++j)
            ans += mp[sum[j] ^ sum[i]];  //如果前面不存在值为区间异或和的值mp[]为0
    }
    printf("%lld\n", ans);
    return 0;
}