【异或和之差——Trie，DP】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int lmax[N], lmin[N], rmax[N], rmin[N];
int ltr[1 << 22][3], rtr[1 << 22][3], idx;
int n, a[N], la[N], ra[N];
void add(int x, int tr[][3])
{
    int p = 0;
    for (int i = 20; i >= 0; i--)
    {
        int u = (x >> i) & 1;
        if (tr[p][u])
            p = tr[p][u];
        else
            p = tr[p][u] = ++idx;
    }
}
int findmax(int x, int tr[][3])
{
    int retv = 0, p = 0;
    for (int i = 20; i >= 0; i--)
    {
        int u = (x >> i) & 1;
        if (tr[p][!u])
        {
            retv += 1 << i;
            p = tr[p][!u];
        }
        else
            p = tr[p][u];
    }

    return retv;
}
int findmin(int x, int tr[][3])
{
    int retv = 0, p = 0;
    for (int i = 20; i >= 0; i--)
    {
        int u = (x >> i) & 1;
        if (tr[p][u])
            p = tr[p][u];
        else
        {
            p = tr[p][!u];
            retv += 1 << i;
        }
    }

    return retv;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 0; i <= n+1; i++) //最值计算需要涉及两个边界
    {
        lmax[i] = rmax[i] = 0;
        lmin[i] = rmin[i] = inf;
    }
    
    add(0, ltr); //压入la[0]
    for (int i = 1; i <= n; i++)
    {
        la[i] = la[i - 1] ^ a[i];
        lmax[i] = max(lmax[i - 1], findmax(la[i], ltr));
        lmin[i] = min(lmin[i - 1], findmin(la[i], ltr));
        add(la[i], ltr);
    }

    idx = 0;
    add(0, rtr); //压入ra[0]
    for (int i = n; i >= 1; i--)
    {
        ra[i] = ra[i + 1] ^ a[i];
        rmax[i] = max(rmax[i + 1], findmax(ra[i], rtr));
        rmin[i] = min(rmin[i + 1], findmin(ra[i], rtr));
        add(ra[i], rtr);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, lmax[i] - rmin[i + 1]);
        ans = max(ans, rmax[i + 1] - lmin[i]);
    }

    cout << ans;
}