665 E. Beautiful Subarrays(字典树与异或性质)

传送门

首先确定肯定使用字典树

然后因为异或的性质有

那么只需要把所有的前缀插入字典树

然后枚举端点去字典树上找有多少个即可

也就是对每一个都去字典树上找有多少个前缀满足条件

那么最后答案需要除以,因为每个一可以作为字典树上的前缀,也可以作为

值得一提的是需要把0插入进去

因为允许存在

那么我们也对前缀去字典树上查询,因为最后的答案是除以二的

如何查询???

因为是二进制数比较大小,所以当的这一位是时

异或值必须是,否则无解,继续往下查询

当的这一位不是时

异或值是,那么直接累加符合条件的前缀个数

然后异或值是,继续查询

最后返回符合条件的个数即可

时间复杂度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e7+10;
const int N = 1e6+10;
int id,n,k,num[maxn],zi[maxn][2],a[N];
ll ans;
void insert(int x)
{
    int now = 0;
    for(int i=30;i>=0;i--)
    {
        int u = (x>>i)&1;
        if( zi[now][u]==0 )    zi[now][u] = ++id;
        now = zi[now][u];
        num[now]++;//标记这个节点下有多少儿子 
    }
}
int ask(int x)
{
    int now = 0,ans = 0;
    for(int i=30;i>=0;i--)
    {
        int u = (x>>i)&1;
        if( zi[now][u^1] )//这一位可以为1
        {
            if( (k>>i)&1 )    now = zi[now][u^1];//k这一位也有1,必须为1 
            else//k这一位没有 
            {
                ans += num[zi[now][u^1]];
                if( zi[now][u] )    now = zi[now][u];
                else    return ans;
            }
        }
        else//只能为0 
        {
            if( (k>>i)&1 )    return ans;
            else    now = zi[now][u];
        }
    }
    ans += num[now];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    int now = 0;  insert( now );
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        now ^= a[i];    insert( now );
    }
    now = 0;
    for(int i=1;i<=n;i++)
        now ^= a[i],ans += ask( now );
    ans += ask(0);
    cout << ans/2;
}

```