Beautiful Subarrays

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;
}