P13895 题解

· · 题解

看到“选择两个不相交的子段”，想到经典 trick：两边分开做，最后统计答案。

假设我们知道了对于任意一个 i，1\sim i（称其为左边）和 i+1\sim n（称其为右边）的子段分别的最大异或和、最小异或和，我们直接枚举 i，然后答案就是左边的最大值减右边最小值，右边的最大值减左边最小值中的 max。

rep(i, 1, n - 1)
{
    int s1 = maxl[i] - minr[i + 1];
    int s2 = maxr[i + 1] - minl[i];
    //minl, maxl, minr, maxr 分别表示两边的最小最大异或和
    ans = max(ans, max(s1, s2));
}

考虑如何求这四个数组。

我们先求左边的情况，右边的情况可以类比。

设 s 为 a 的前缀异或和数组，我们注意到 \oplus_{i = l}^{r} a_i=s_r\oplus s_{l - 1}

于是我们就把一段区间的异或和转化为了两个数的异或的值。

我们枚举右端点 r，然后找一个 l 使得 s_r\oplus s_{l - 1} 最大（或者最小），可以用 01-trie 解决。

注意这样可以计算到所有区间，右边的情况类比就行了。

cin >> n;
r(n) cin >> a[i], la[i] = la[i - 1] ^ a[i]; 
reb(i, n, 1) ra[i] = ra[i + 1] ^ a[i];
maxl[0] = maxr[n + 1] = 0;
minl[0] = minr[n + 1] = INT_MAX;
tl.insert(0), tr.insert(0);
r(n) // 枚举右端点 i
{
    int k1 = tl.findmx(la[i]);
    int k2 = tl.findmn(la[i]);
    tl.insert(la[i]);
    maxl[i] = max(maxl[i - 1], k1);
    minl[i] = min(minl[i - 1], k2);
}
reb(i, n, 1)
{
    int k1 = tr.findmx(ra[i]);
    int k2 = tr.findmn(ra[i]);
    tr.insert(ra[i]);
    maxr[i] = max(maxr[i + 1], k1);
    minr[i] = min(minr[i + 1], k2);
}

::::info[01-trie 封装代码]

struct Trie
{
    int tr[N << 3][2], cnt = 0;
    void insert(int x)
    {
        int p = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (!tr[p][vl])
                tr[p][vl] = ++cnt;
            p = tr[p][vl];
        }
    }
    int findmx(int x)
    {
        int p = 0, res = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (tr[p][vl ^ 1])
                p = tr[p][vl ^ 1], res |= (1 << i);
            else p = tr[p][vl];
        }
        return res;
    }
    int findmn(int x)
    {
        int p = 0, res = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (tr[p][vl])
                p = tr[p][vl];
            else p = tr[p][vl ^ 1], res |= (1 << i);
        }
        return res;
    }
} tl, tr;

::::

::::info[完整 AC 代码]

#include<bits/stdc++.h>
// #define int long long
#define r(x) for (int i = 1; i <= x; i++)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define reb(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

const int N = 2e6 + 50;
int n, q, x, a[N], ans, maxl[N], maxr[N];
int la[N], ra[N], k, minl[N], minr[N];

struct Trie
{
    int tr[N << 3][2], cnt = 0;
    void insert(int x)
    {
        int p = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (!tr[p][vl])
                tr[p][vl] = ++cnt;
            p = tr[p][vl];
        }
    }
    int findmx(int x)
    {
        int p = 0, res = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (tr[p][vl ^ 1])
                p = tr[p][vl ^ 1], res |= (1 << i);
            else p = tr[p][vl];
        }
        return res;
    }
    int findmn(int x)
    {
        int p = 0, res = 0;
        reb(i, 20, 0)
        {
            bool vl = x & (1 << i);
            if (tr[p][vl])
                p = tr[p][vl];
            else p = tr[p][vl ^ 1], res |= (1 << i);
        }
        return res;
    }
} tl, tr;

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    r(n) cin >> a[i], la[i] = la[i - 1] ^ a[i]; 
    reb(i, n, 1) ra[i] = ra[i + 1] ^ a[i];
    maxl[0] = maxr[n + 1] = 0;
    minl[0] = minr[n + 1] = INT_MAX;
    tl.insert(0), tr.insert(0);
    r(n)
    {
        int k1 = tl.findmx(la[i]);
        int k2 = tl.findmn(la[i]);
        tl.insert(la[i]);
        maxl[i] = max(maxl[i - 1], k1);
        minl[i] = min(minl[i - 1], k2);
    }
    reb(i, n, 1)
    {
        int k1 = tr.findmx(ra[i]);
        int k2 = tr.findmn(ra[i]);
        tr.insert(ra[i]);
        maxr[i] = max(maxr[i + 1], k1);
        minr[i] = min(minr[i + 1], k2);
    }
    rep(i, 1, n - 1)
    {
        int s1 = maxl[i] - minr[i + 1];
        int s2 = maxr[i + 1] - minl[i];
        ans = max(ans, max(s1, s2));
    }
    cout << ans << "\n";
    return 0;
}

::::