摘要
Title: 3485. 最大异或和
Tag: Trie、可持久化Trie
Memory Limit: 64 MB
Time Limit: 1000 ms

3485. 最大异或和

题意

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

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

可持久化：通俗来讲，可持久化就是指一个数据结构能查询历史记录，我们需要借助该结构，查询过去版本中有用的信息
比如，最大异或和问题，一开始的版本是要求x和整个区间的数中挑选一个异或和最大，而如果要x和某个区间的数中挑选一个异或和最大，按以前的思路，是这个区间也得单独建一个Trie，但如果多个区间呢？那这里就需要建立可持久化的Trie树

首先说一下思路，在前缀异或和数组中，就是在每个数的前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;
        else
            x = son[x][u];
    }
    return a[ver[x]] ^ v;
}

signed main()
{
    IOS;
    cin >> n >> m;
    // init
    root[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;
}

3485. 最大异或和

题意

思路

代码