Beautiful Subarrays

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

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

这里我们可以去找一个,满足,这个时候大于等于的数就是满足要求的数了,

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

分四种情况:

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

    与a异或之后会变大,的位对答案有贡献,所以我们加上答案,然后到当前位上是0的地方去继续寻找。

  • a的当前位二进制数是0, k的当前位二进制数是1,我们要使查找值不变小,一定要到当前位是1上去找,这个时候的位对答案是没有贡献。

  • a的当前位二进制数是1, k的当前位二进制数是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;
}