Xorto 题解_牛客博客

一.闲话

检查n久，发现数组开小，难受至极qwq

本题解的做法较大佬做法比较复杂，不过好处在于，时空复杂度与 $a_i$ 的大小无关qwq

二.题解

读题，发现题目要求有多少对区间满足两个不重叠非空区间异或和为0

因为有个众人皆知的东西：

两个数异或和为0，当且仅当两个数大小相同

所以其实此题就转化为了：

求有多少对不重叠且异或值相同的区间

看数据范围，发现n<=1000

于是我们可以考虑直接暴力计算全部区间各自的异或和，再把值相同的分为一组，计算各自不重叠的区间的对数。

现在，假设我们分组分好了，也就是说这里有若干个区间：

$(l_1,r_1),(l_2,r_2)...(l_k,r_k)$

我们要求有多少个不重叠的区间对

画个图发现，若两个区间 $i,j(i<j)$ 不重叠，则一定满足：

$r_i<l_j或者r_j<l_i$

为了方便，我们将这些区间按l递增的顺序进行排序

则，如果两个区间不重叠，则一定满足：

$r_i<l_j$

所以，我们发现，与区间 $i$ 重叠的区间 $j$ ，若 $j\in(1-(i-1))$ ,则一定有 $r_j<l_i$ 所以，我们这里就可以直接开一个权值线段树来做，每次统计 $(1-(l_i-1))$ 的数的个数，再把 $r_i$ 放进去，即可

至于如何按异或值分组，我们可以开个结构体，将所有区间左右端点，区间异或值放进去

按异或值为第一关键字，左端点为第二关键字sort一遍后，异或值一样的就自然的在一段连续的下标中了

但是，我们不可能每有一组就新增一个权值线段树，空间容易爆，所以，我们每次打个表示清空的laz标记，即可~

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5001;
int a[N];
struct node{
    int w,l,r;
}t[1000001];
int W[N<<2];bool laz[N<<2];
inline bool kkk(node x,node y){
    return x.w!=y.w?x.w<y.w:x.l<y.l;
}
inline void down(int now){
    if(laz[now]){
        W[now<<1]=W[now<<1|1]=laz[now]=0;
        laz[now<<1]=laz[now<<1|1]=1;
    }
}
inline void insert(int now,int l,int r,int x){
    down(now);
    ++W[now];
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        insert(now<<1,l,mid,x);
    }else{
        insert(now<<1|1,mid+1,r,x);
    }
}
inline int find(int now,int l,int r,int lc,int rc){
    down(now);
    if(lc<=l&&r<=rc){
        return W[now];
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res+=find(now<<1,l,mid,lc,rc);
    }
    if(rc>mid){
        res+=find(now<<1|1,mid+1,r,lc,rc);
    }
    return res;
}
signed main(){
    int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    int e=0;
    for(int i=1;i<=n;++i){
        int val=0;
        for(int j=i;j<=n;++j){
            val^=a[j];
            t[++e]=(node){val,i,j};
        }
    }
    sort(t+1,t+e+1,kkk);
    int ans=0;
    insert(1,1,n,t[1].r);
    for(int i=2;i<=e;++i){
        if(t[i].w==t[i-1].w){
            if(t[i].l>1){//小特判下，防止无限递归
                ans+=find(1,1,n,1,t[i].l-1);
            }
        }else{
            laz[1]=1;W[1]=0;
        }
        insert(1,1,n,t[i].r);
    }
    printf("%lld",ans);
    return 0;
}