题目描述

难度分:$2200$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^{12})$。

选择$a$的一个前缀（可以为空）和一个后缀（可以为空），要求前缀后缀不相交。

输出所选数字的异或和的最大值。

输入样例$1$

2
1 2

输出样例$1$

3

输入样例$2$

3
1 2 3

输出样例$2$

3

输入样例$3$

2
1000 1000

输出样例$3$

1000

算法

枚举+01字典树按位贪心

这个题的思路比较简单，其实就是“算法基础课最大异或对”那个题的拓展，先将所有的后缀异或和（$sufXor_i=\oplus_{k=i}^{n}a[k]$，$i \in [1,n]$，注意还要放入一个$0$，防止后缀为空的情况）都放到一个01字典树中。并给字典树实现一个特殊的$search$函数，$search(x)$查询的是字典树中所有元素与$x$异或能够得到的最大值，这个函数的原理就是最大异或对那个题按位贪心的思路。

然后枚举前缀，注意到前缀和后缀是可以为空的，先初始化答案$ans$为“前缀为空”与“后缀为空”时的较大值。然后考虑前后缀都不为空的情况，枚举前缀的右端点$i$，当遍历到$a[i]$时，设此时的前缀异或和为$preXor=\oplus_{k=1}^{i}a[k]$，将$sufXor_i$从字典树中删除以保证前后缀不重叠，维护$ans$与$search(preXor)$的最大值即可。

复杂度分析

时间复杂度

01字典树的插入，删除和查询都是较大的常数操作，仅与数字的二进制位有关，本题的数据范围在$10^{12}$以内，因此迭代的深度最大不会超过$k=40$，这个常数操作的时间复杂度为$O(k)$。枚举所有前缀的时间复杂度为$O(n)$，因此算法整体的时间复杂度也为$O(kn)$。

空间复杂度

最差情况下每个数$a[i]$都需要$40$个位来存储，因此额外空间复杂度为$O(kn)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N];
int n;

class TrieNode {
public:
    int pass;
    TrieNode* next[2];
    TrieNode() {
        pass = 0;
        next[0] = NULL;
        next[1] = NULL;
    }
};

class Trie {
public:
    const int HEIGHT = 41;
    TrieNode* root = new TrieNode();

    void insert(LL x) {
        TrieNode* cur = root;
        for(int i = HEIGHT; i >= 0; i--) {
            int bit = x>>i&1;
            if(cur->next[bit] == NULL) {
                cur->next[bit] = new TrieNode();
            }
            cur = cur->next[bit];
            cur->pass++;
        }
    }

    void erase(LL x) {
        TrieNode* cur = root;
        for(int i = HEIGHT; i >= 0; i--) {
            int bit = x>>i&1;
            if(cur->next[bit]->pass-- == 1) {
                cur->next[bit] = NULL;
                return;
            }
            cur = cur->next[bit];
        }
    }

    LL search(LL x) {
        TrieNode* cur = root;
        LL y = 0;
        for(int i = HEIGHT; i >= 0; i--) {
            int bit = x>>i&1;
            if(cur->next[1 - bit]) {
                y = (y<<1ll) + (1 - bit);
                cur = cur->next[1 - bit];
            }else {
                y = (y<<1ll) + bit;
                cur = cur->next[bit];
            }
        }
        return x^y;
    }
};

int main() {
    scanf("%d", &n);
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        ans ^= a[i];
    }
    LL suf_xor = 0;
    Trie* trie = new Trie();
    trie->insert(suf_xor);
    for(int i = n; i >= 1; i--) {
        suf_xor ^= a[i];
        trie->insert(suf_xor);
    }
    LL pre_xor = 0;
    ans = max(ans, trie->search(0));
    for(int i = 1; i < n; i++) {
        pre_xor ^= a[i];
        trie->erase(suf_xor);
        suf_xor ^= a[i];
        ans = max(ans, trie->search(pre_xor));
    }
    printf("%lld\n", ans);
    return 0;
}