Nikitosh 和异或

· · 个人记录

「一本通 2.3 例 3」Nikitosh 和异或

首先，题意是找出左一端、右一段异或和，使他们的加和最大

可以枚举中间的断点i，然后求i的左边最大异或和+右边最大异或和的max即可

由此我们考虑如何维护出每一个位置i的左右最大异或和：

问题有一个难点，trie树有可能前后不适用，所以要满足前面加入树的后面也可以用到

而且我们的trie树只能做到选出两个数的异或和，仔细想想的话 我们可以维护一个异或前缀和，并利用异或和的自反性

设i<j，那么sum[1,i-1] ⊕ sum[1,j]就等于sum[i,j]

综上所述，我们就可以想出一个线性思路：

从左到右或者从右到左扫，同时维护一个从起点到当前指针的sum

对于每个位置，将当前sum扔入树，查找当前sum可以配对的最大异或和，更新答案

维护两遍以后，再按照最开始说的思路求左右两边max即可

没加快读，加了还能更快

class Solution_Case
{
    /*
    整体上比较有难度
    题意是找出左一端、右一段异或和，使他们的加和最大
    可以枚举中间的断点i，然后求 i的左边最大异或和+右边最大异或和 的max即可

    由此我们考虑如何维护出每一个位置i的左右最大异或和：
    问题有一个难点，trie树有可能前后不适用，所以要满足前面加入树的后面也可以用到
    而且我们的trie树只能做到选出两个数的异或和，仔细想想的话
    我们可以维护一个异或前缀和，并利用异或和的自反性
    设i<j，那么sum[1,i-1]^sum[1,j]就等于sum[i,j]

    综上所述，我们就可以想出一个线性思路：
    从左到右或者从右到左扫，同时维护一个从起点到当前指针的sum
    对于每个位置，将当前sum扔入树，查找当前sum可以配对的最大异或和，更新答案
    维护两遍以后，再按照最开始说的思路求左右两边max即可
    */
};

#include<bits/stdc++.h>
#define N 400005
#define BetterIO \
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0)
using namespace std;

int trie[N * 33][2];    //2个子节点
int tot;
int n, a[N], L[N], R[N];

void Insert(int x)
{
    //插入树，根到叶子 为 数的左到右
    int p = 0;
    for (int i = 31; i >= 0; i--)
    {
        int u = (x >> i) & 1; //获取每个二进制位，依次为高位到低位
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
    }
}

int Find(int x)
{
    //查找时候，尽量取不一样的数位，这样异或后的结果是1
    int p = 0, ans = 0;
    for (int i = 31; i >= 0; i--)
    {
        int u = (x >> i) & 1;
        if (trie[p][!u]) ans = ans * 2 + 1, p = trie[p][!u]; //反位有数，那么取反
        else ans *= 2, p = trie[p][u];  //反位无数，那么取本位
    }
    return ans;
}

signed main()
{
    BetterIO;
    cin >> n;
    Insert(0);
    for (int i = 1, sum = 0; i <= n; i++)   //从左向右
    {
        cin >> a[i];
        sum ^= a[i];
        Insert(sum);
        L[i] = max(L[i - 1], Find(sum));
    }
    tot = 0;
    memset(trie, 0, sizeof trie);
    Insert(0);
    for (int i = n, sum = 0; i > 0 ; i--)   //从右往左
    {
        sum ^= a[i];
        Insert(sum);
        R[i] = max(R[i + 1], Find(sum));
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max({ans, L[i] + R[i + 1], L[i - 1] + R[i]});
    }
    cout << ans;
    return 0;
}