【每日一题】1月8日题目精讲

题号 NC111446
名称 Beautiful Subarrays
来源 CF665E
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

有

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

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

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

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

分四种情况:

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

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月14日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴