3485. 最大异或和

Powered by:NEFU AB-IN

Link

3485. 最大异或和

• 题意

  给定一个非负整数数列 a，初始长度为 N。
  请在所有长度不超过 M的连续子数组中，找出子数组异或和的最大值。
  子数组的异或和即为子数组中所有元素按位异或得到的结果。
  注意：子数组可以为空。

• 思路

  可持久化Trie 非递归模板
  个人认为是最通俗易懂、和简洁的版本！
  代码讲解 Link

  首先说一下思路，在前缀异或和数组中，就是在每个数的前m-1区间内，找异或的最大值
  简要介绍一下各个数组和变量的含义

  • ver 其实就是version的意思，代表这个结点id是属于哪个版本的树
    • 下标是结点id
    • 值是树的id（其实本题中也和原数组a的id对应）
  • root 比如root[i] = 1，代表第i颗树的根节点id为1
    • 下标是树的id
    • 值是结点id

  比如 1 2 3 4 5 （这五个数为下标，以5为例），查询的时候便是，query(root[4], 3, a[5])

  • 为什么是3呢？
    • 因为是前缀异或和数组，l需要减一
    • 其次需要注意，这个值必须大于等于0，就是在查询的时候，和0取一个最大值
  • 为什么是root[4]
    • 其实root[5]也可以，因为5这个下标的值不可能取，毕竟自己异或自己为0，能省一步是一步

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-02-27 09:36:13
  * @FilePath: \Acwing\3485\3485.cpp
  * @LastEditTime: 2023-02-27 20:03:43
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 1e5 + 10, M = N * 32, INF = 0x3f3f3f3f;int ver[M], root[N], son[M][2], idx;
  int n, m;
  int a[N];void insert(int x, int y, int k)
  // x为当前树的根节点编号，y为上一个树的根节点编号，k为第几棵树
  {ver[x] = k;for (int i = 30; i >= 0; --i){int u = a[k] >> i & 1;son[x][!u] = son[y][!u];son[x][u] = ++idx;x = son[x][u];y = son[y][u];ver[x] = k;}
  }int query(int x, int L, int v)
  // x为当前树的根节点，L为不能超越的树编号左边界，v为输入函数的定值
  {for (int i = 30; i >= 0; --i){int u = v >> i & 1;if (ver[son[x][!u]] >= L)x = son[x][!u]; // res += 1 << i;elsex = son[x][u];}return a[ver[x]] ^ v;
  }signed main()
  {IOS;cin >> n >> m;// initroot[0] = ++idx;ver[0] = -1;insert(root[0], 0, 0);for (int i = 1; i <= n; ++i){cin >> a[i];a[i] ^= a[i - 1];root[i] = ++idx;insert(root[i], root[i - 1], i);}int res = 0;for (int i = 1; i <= n; ++i){res = max(res, query(root[i], max(0, i - m), a[i]));}cout << res << '\n';return 0;
  }