Beautiful Subarrays_牛客博客

Beautiful Subarrays

有 $a_i\bigoplus a_{i + 1} \bigoplus ……\bigoplus a_{n} = (a_1 \bigoplus a_2 \bigoplus……\bigoplus a_{n}) \bigoplus (a_1 \bigoplus a_2 \bigoplus …… \bigoplus a_{i - 1})$

所以我们可以先求一遍异或前缀和，然后再通过枚举右端点，去查找有多少个左端点符合要求。

假设我们当前枚举到 $i$ 这个位置，前 $i$ 个数的异或前缀和是 $a$ ，我们要查找异或值大于等于 $k$ 的,

这里我们可以去找一个 $x$ ，满足 $a \bigoplus k = x$ ，这个时候大于等于 $x$ 的数就是满足要求的数了，

这个操作我们可以通过一颗 $01trie$ 树来实现。

分四种情况:

a 的当前位二进制数是0，k的当前位二进制数也是0，如果我们选择一个数的当前位是1，

与a异或之后会变大， $1$ 的位对答案有贡献，所以我们加上答案，然后到当前位上是0的地方去继续寻找。
a的当前位二进制数是0， k的当前位二进制数是1，我们要使查找值不变小，一定要到当前位是1上去找，这个时候 $0$ 的位对答案是没有贡献。
a的当前位二进制数是1， k的当前位二进制数是0，如果我们选择 $0$ ，异或结果变大， $0$ 的位对答案有贡献，所以加上答案，

走到当前位是1的地方去继续寻找答案。
a的当前位二进制数是1， k的当前位二进制也是1，这个时候要保证异或结果不变小，只能到当前位是0的地方去寻找。

最后再特判一下刚好相等的情况就OK了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e7 + 10;

int trie[N][2], tot, num[N];

void insert(int x) {
  int rt = 0;
  for(int i = 30; i >= 0; i--) {
    int now = x >> i & 1;
    if(!trie[rt][now]) {
      trie[rt][now] = ++tot;
    }
    rt = trie[rt][now];
    num[rt]++;
  }
}

int find(int a, int b) {
  int ans = 0, rt = 0;
  for(int i = 30; i >= 0; i--) {
    int u = a >> i & 1, v = b >> i & 1;
    if(!u) {
      if(v) {
        if(!trie[rt][1]) return ans;
        rt = trie[rt][1];
      }
      else {
        ans += num[trie[rt][1]];
        if(!trie[rt][0]) return ans;
        rt = trie[rt][0];
      }
    }
    else {
      if(!v) {
        ans += num[trie[rt][0]];
        if(!trie[rt][1]) return ans;
        rt = trie[rt][1];
      }
      else {
        if(!trie[rt][0]) return ans;
        rt = trie[rt][0];
      }
    }
  }
  return ans + num[rt];
}

const int N1 = 1e6 + 10;

int a[N1], n, k;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] ^= a[i - 1];
  }
  insert(0);
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    int temp = find(a[i], k);
    ans += temp;
    insert(a[i]);
  }
  printf("%lld\n", ans);
  return 0;
}