每日一题Xorto_牛客博客

题意：给定两个数组，求多少个不相交区间异或值为0；
题解：两个区间异或为0，意思即可变为：两个区间各自异或相等，即若选了区间 $[i,j],[x,y]$ $(j<x)$
则满足 $a_i$ ^ $a_{i+1}$ ^ $a_{i+2}\cdots$ ^ $a_j=a_x$ ^ $a_{x+1}\cdots a_y$
那么我们只需要将要选的区间见视为左边选一个区间，右边选一个区间，各自区间内异或值相等即产生贡献，所以我们可以一边枚举左边的区间异或值，同时记录右边区间异或值的个数，然后看右边区间与枚举的异或值相等的有多少个区间，将他加到贡献中即可。具体看代码注释。
时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=2e5;
const int mod=1e9+7;
const double eps=1e-6;
const double pi=3.14159265358979;
int inv2;
using namespace std;
ll in[MX+7],pr[MX+7],prni[MX+7],F[MX+7];
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
int dcmp(double x){
    if(x>eps)return 1;
    return x<-eps?-1:0;
}
int a[MX],b[MX],c[MX];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>a[i];
  }
  ll sum=0;
  for(int i=n;i>=1;i--)//枚举左边区间的右端点
  {
      int x=0;
      for(int j=i;j>=1;j--)//枚举左边的区间的左端点
      {
          x^=a[j];
          sum+=b[x];//异或为x的右边区间个数
      }
      for(int k=n;k>=i;k--)//右边区间没记录的区间异或值，即以i为左端点的区间，加上，就可以更新所有右边区间的各个异或值个数。
      {
          c[k]^=a[i];//c记录的是区间[k,i]的异或值，并逐步更新
          b[c[k]]++;
      }
  }
  cout<<sum<<endl;
}