256 最大异或和（可持久化Trie树）

ゝ一世哀愁。 2022-09-09 04:44 129阅读 0赞

**1. 问题描述：**

给定一个非负整数序列 a，初始长度为 N。  
有 M 个操作，有以下两种操作类型：  
A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大 1。  
Q l r x：询问操作，你需要找到一个位置 p，满足 l ≤ p ≤ r，使得：a\[p\] xor a\[p+1\] xor … xor a\[N\] xor x 最大，输出这个最大值。

**输入格式**

第一行包含两个整数 N，M，含义如问题描述所示。  
第二行包含 N 个非负整数，表示初始的序列 A。  
接下来 M 行，每行描述一个操作，格式如题面所述。

**输出格式**

每个询问操作输出一个整数，表示询问的答案。  
每个答案占一行。

**数据范围**

N，M ≤ 3×10 ^ 5，0 ≤ a\[i\] ≤ 10 ^ 7。

**输入样例：**

5 5  
2 6 4 3 6  
A 1  
Q 3 5 4  
A 4  
Q 5 7 0  
Q 3 6 6

**输出样例：**

4  
5  
6

来源：[https://www.acwing.com/problem/content/258/][https_www.acwing.com_problem_content_258]

**2. 思路分析：**

这道题目属于**可持久化Trie树**的题目，**可持久化**是一种思想，而且并不是所有的数据结构都是支持可持久化的，可持久化的一个前提是数据结构本身的拓扑结构是不变的，例如Trie树，树状数组，线段树等这些数据结构本身的拓扑结构是不变的（例如线段树本身的拓扑结构是不变的，解决的问题不同只需要修改线段树节点维护的信息和维护信息的代码即可），例如平衡树本身的拓扑结构是会发生变化的所以一般来说平衡树是不容易可持久化的。可持久化是一种思想，类似于git的版本控制，git会记录下之前所有的历史版本这样当我们想回退到某一个历史版本的时候可以直接回退到之前的历史版本，可持久化思想也是类似的，对于当前的节点的某一个分支若上一个版本存在那么当前节点的对应分支直接拷贝上一个版本即可，也即当前节点的某一个分支连上上一个版本对应的分支即可，对于当前节点的这一条分支是需要重建的。这道题目类似于之前力扣的[421][]题，421题求解的是数组中两个数字的最大异或值，这里求解的是区间\[l - 1，r - 1\]中的某一个位置p - 1，我们可以先处理一下异或前缀和：sn ^ x是固定值所以要想使得结果最大那么需要在\[l - 1，r - 1\]区间中选择一个位置p - 1使得异或的结果最大，所以这里求解的位置p - 1是有一个限制的。我们可以利用可持久化思想使得构建出的Trie树可以回退到某一个版本（对应区间右端点的版本），这样对于区间右端点的限制就满足了，接下来需要选择的位置是在l - 1的右边的，等价于节点下标的最大值大于等于l - 1，我们在插入节点的时候使用max\_id来维护节点的最大下标即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

![20210829210143870.png][]

**3. 代码如下：**

**c++：**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int N = 600010, M = N * 25;
    
    int n, m;
    int s[N];
    int tr[M][2], max_id[M];
    // root维护当前的版本(root[i]表示第i个节点), idx用来唯一标识Trie树种的节点, 通过这个idx我们可以定位在Trie树中的某一个节点
    int root[N], idx;
    
    // i表示当前的下标, k表示当前递归的数字的哪一位, p为上一个历史版本, q为下一个历史版本
    void insert(int i, int k, int p, int q)
    {
        if (k < 0)
        {
            max_id[q] = i;
            return;
        }
        int v = s[i] >> k & 1;
        // 上一个版本的某一个存在那么当前版本的对应分支连上去即可
        if (p) tr[q][v ^ 1] = tr[p][v ^ 1];
        tr[q][v] = ++ idx;
        insert(i, k - 1, tr[p][v], tr[q][v]);
        // 求解当前节点的最大下标
        max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
    }
    
    int query(int root, int C, int L)
    {
        // root为当前的历史版本
        int p = root;
        for (int i = 23; i >= 0; i -- )
        {
            // 求解c当前的第i位数字
            int v = C >> i & 1;
            if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
            else p = tr[p][v];
        }
    
        return C ^ s[max_id[p]];
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        max_id[0] = -1;
        root[0] = ++ idx;
        insert(0, 23, 0, root[0]);
        for (int i = 1; i <= n; i ++ )
        {
            int x;
            scanf("%d", &x);
            s[i] = s[i - 1] ^ x;
            root[i] = ++ idx;
            // 插入当前的节点
            insert(i, 23, root[i - 1], root[i]);
        }
    
        char op[2];
        int l, r, x;
        while (m -- )
        {
            scanf("%s", op);
            if (*op == 'A')
            {
                scanf("%d", &x);
                n ++ ;
                s[n] = s[n - 1] ^ x;
                root[n] = ++ idx;
                insert(n, 23, root[n - 1], root[n]);
            }
            else
            {
                scanf("%d%d%d", &l, &r, &x);
                printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
            }
        }
        return 0;
    }

[https_www.acwing.com_problem_content_258]: https://www.acwing.com/problem/content/258/
[421]: https://blog.csdn.net/qq_39445165/article/details/118306883
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/55bb2707162f4aecb7fa67341b6f6079.png
[20210829210143870.png]: /images/20220829/5c0400b699f5421f85d18ea230416cb8.png