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

形式化题目

给定含 $N$ 个元素的数组 $A$ （下标从 $1$ 开始），求下式的最大值：

\left(A_{l_1} \oplus A_{l_1+1} \oplus \cdots \oplus A_{r_1}\right) + \left(A_{l_2} \oplus A_{l_2+1} \oplus \cdots \oplus A_{r_2}\right)

其中两段互不相交：

1 \leqslant l_1 \leqslant r_1 < l_2 \leqslant r_2 \leqslant N

即选出两个非空、不相交的连续子数组，使它们的异或和之和最大。

样例： $N=5$ ， $A = [1,2,3,1,2]$ ，输出 $6$ 。达到 $6$ 的四元组有 $(1,2,3,3)$ （ $1\oplus2=3$ 加 $A_3=3$ ）、 $(1,2,4,5)$ （ $3$ 加 $1\oplus2=3$ ）、 $(3,3,4,5)$ （ $3$ 加 $3$ ）。

正解

思路

朴素做法：枚举两段的所有组合。 子数组共 $\Theta(N^2)$ 个，两两配对（要求 $r_1 < l_2$ ）是 $\Theta(N^4)$ 量级的组合。即使先用前缀异或把单次求值压到 $O(1)$ ，组合数不变——原题 $N$ 最大 $4 \times 10^5$ ，完全不可行。真正需要的不是每对子数组的值，而是两类极值：每个前缀、后缀区间内各自的"最大子数组异或"。

第一层优化：分割点拆分。 两段不相交，就一定存在某个分割点 $k$ （ $1 \leqslant k < N$ ）把它们隔开：左段完全落在 $A[1..k]$ ，右段完全落在 $A[k+1..N]$ 。左右两段互不制约，于是

\text{答案} = \max_{1 \leqslant k < N} \big(f(k) + g(k+1)\big)

其中 $f(k)$ 是 $A[1..k]$ 内的最大子数组异或， $g(i)$ 是 $A[i..N]$ 内的最大子数组异或。用样例 $A=[1,2,3,1,2]$ 把每个分割点算一遍：

分割点 $k$	$f(k)$ ： $A[1..k]$ 内最大子数组异或	$g(k+1)$ ： $A[k+1..5]$ 内最大子数组异或	两段之和
1	1	3	4
2	3	3	6
3	3	3	6
4	3	2	5

答案 $6$ 在 $k=2,3$ 处取得，恰好对应样例给出的三组最优四元组： $(1,2,3,3)$ 对应 $k=2$ ， $(1,2,4,5)$ 与 $(3,3,4,5)$ 的两段分别落在 $k=3$ 的两侧。这层变换把 $\Theta(N^4)$ 的"段对组合"降成"求 $f$ 、求 $g$ 、再 $O(N)$ 扫一遍合并"。

第二层优化：前缀异或。 记 $P_0 = 0$ ， $P_i = A_1 \oplus \cdots \oplus A_i$ ，中间项两两抵消：

\mathrm{xor}(A[l..r]) = P_r \oplus P_{l-1}

于是 $f(k) = \max_{1 \leqslant r \leqslant k} h(r)$ ，其中 $h(r) = \max_{0 \leqslant j < r} \left(P_r \oplus P_j\right)$ ——"以 $r$ 结尾的最大子数组异或"就是拿 $P_r$ 去和所有更早的前缀异或配对求最大异或。瓶颈集中到了这一步：逐个 $j$ 扫描求 $h(r)$ ，总代价 $O(N^2)$ ， $N=4\times10^5$ 时约 $1.6\times10^{11}$ 次运算，仍然不可行。

第三层优化：01-Trie 上的贪心。 把 $P_0, P_1, \dots, P_{r-1}$ 按二进制从高位到低位插入一棵 01-Trie（每层一个二进位，往左是 $0$ 、往右是 $1$ ），查询 $P_r$ 时逐层决策：设当前位为 $b$ ，若"反向位 $1-b$ "的儿子存在就走过去（该位异或得 $1$ ），否则只能顺 $b$ 的儿子走（该位得 $0$ ）。贪心正确性来自高位的权重：第 $s$ 位的收益 $2^s$ 严格大于所有低位之和 $2^s - 1$ ，所以"高位能取 $1$ 就先取 $1$ "不会被任何低位组合反超。单次查询/插入都是 $O(B)$ ， $B$ 为值域位数（ $B \leqslant 30$ ）。

以样例演示： $B = \mathrm{bit\_length}(\max A) = 2$ ，查询 $P_2 = 3 = 11_2$ 时 Trie 里只有 $P_0 = 00$ 、 $P_1 = 01$ ：

graph TD
    R["根"] -->|"0"| N1["内部结点：前缀 0"]
    N1 -->|"0"| L0["叶：P0 = 00"]
    N1 -->|"1"| L1["叶：P1 = 01"]
    R -.->|"1：尚不存在"| X["虚位"]

第 $1$ 位 $b=1$ ，想找反向的 $0$ 号儿子——存在，走过去并把该位记 $1$ ；第 $0$ 位 $b=1$ ，反向的 $0$ 号儿子（ $P_0$ 的路径）也存在，再记 $1$ ；累计 $11_2 = 3 = P_2 \oplus P_0$ ，落点是 $P_0$ ，对应子数组 $A[1..2] = 1 \oplus 2 = 3$ 。注意根的 $1$ 号儿子此时并不存在——若 $b=0$ 想找反向的 $1$ 就只能顺着 $0$ 走，这正是"不存在才退让"的含义。

先查后插保证查询 $P_r$ 时集合里只有 $P_0 \dots P_{r-1}$ ：partner 下标 $j < r$ ，对应子数组 $A[j+1..r]$ 非空且右端点恰为 $r$ 。在扫 $f$ 的过程中维护前缀最大值 $f(k) = \max(f(k-1), h(k))$ ，一遍即得所有 $f$ 。

后缀复用与合并。 $g$ 与 $f$ 是同一个函数作用在反转数组上：prefix_best(a[::-1]) 的结果再反转就是 $g$ 。最后 $O(N)$ 扫一遍 $\max_k f(k) + g(k+1)$ 即为答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:05
# update_at: 2026-09-30 13:05

import sys
from array import array
from collections.abc import Iterator
from itertools import accumulate
from operator import xor


def prefix_best(a: list[int], bits: int) -> Iterator[int]:
    """依次产出 best[0..n-1]：best[k] = a[0..k] 里所有子数组异或和的最大值。

    前缀异或 P 满足 xor(a[l..i]) = P[i+1] ^ P[l]：把 P[0..n] 依次喂给 01-Trie，
    每轮先拿 P[i] 查最大异或 partner、再把它自己插入，partner 下标天然更小。
    第一轮（空前缀 P[0]）只插入不产出；逐个 yield 不攒整表，省内存。
    """
    ch = array("i", [0]) * 4       # ch[t<<1|b]：结点 t 的 b 儿子结点号，0 表示没有；int32 平坦数组省内存
    top = 1      # 已用结点的最大编号；0 号空置，1 号是根
    best = 0     # 前缀最大值：至今见过的最大子数组异或
    for i, v in enumerate(accumulate(a, xor, initial=0)):  # v 依次取 P[0]=0, P[1], …, P[n]
        # —— 先查：v 对着集合里已有的前缀异或贪心取最大异或 ——
        t, acc = 1, 0
        for s in range(bits - 1, -1, -1):
            b = v >> s & 1
            w = ch[t + t + (b ^ 1)]  # 最想要与当前位相反的儿子
            if w:
                acc |= 1 << s
                t = w
            else:
                t = ch[t + t + b]
        if acc > best:
            best = acc
        if i:  # 跳过空前缀那一轮（对应空输入，无真实子数组）
            yield best
        # —— 后插：把 v 自己放进集合，供后面的位置查询 ——
        t = 1
        for s in range(bits - 1, -1, -1):
            b = v >> s & 1
            nxt = ch[t + t + b]
            if not nxt:
                top += 1
                if len(ch) < top + top + 2:  # 槽位只在新建结点时变大，按 4MB 块增量扩，避免大块拷贝峰值
                    ch.extend(array("i", [0]) * (1 << 20))
                ch[t + t + b] = top
                nxt = top
            t = nxt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    del data                      # 及时释放迭代器引用，压低峰值内存
    bits = max(1, max(a).bit_length())  # 异或不会超出 max(a) 的最高位
    # right[k]：a[k..n-1] 内的最大子数组异或（int32 数组，比列表省 10MB+）
    right = array("i", prefix_best(a[::-1], bits))
    right.reverse()
    # left 边算边用不落表：答案 = max_k left[k] + right[k+1]（两段以 k 为分割点）
    ans = max(lv + right[k + 1] for k, lv in enumerate(prefix_best(a, bits)) if k + 1 < n)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:10
 * update_at: 2026-10-05 03:17
 */
// 求两个不相交子数组异或和之和的最大值。
// 做法：枚举分割点 k，答案 = max(f(k) + g(k+1))；
// f(k) 是 A[1..k] 内最大子数组异或，g(i) 是 A[i..N] 内最大子数组异或。
// 子数组异或 = 两个前缀异或之异或，于是"以 i 结尾的最大子数组异或"
// 就是拿 P[i] 去 01-Trie 里和更早的所有前缀异或求最大异或（先查后插）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 400005;
const int MAXNODE = 24000100; // ch 槽位数上界：2*((N+1)*B+2)，B <= 30（每结点两个儿子槽）

int n;       // 数组元素个数
int bits;    // 值域二进制位数：异或结果不会超过 max(A) 的最高位
ll a[MAXN];  // 题目给出的数组，下标从 1 开始
ll b[MAXN];  // a 的反转数组，用来复用同一函数求后缀方向的 g
ll pre;      // 扫描过程中的当前前缀异或 P[i] = A[1] ^ ... ^ A[i]
ll f[MAXN];  // f[k]：A[1..k] 内所有子数组异或和的最大值
ll g[MAXN];  // g[k]：A[k..n] 内所有子数组异或和的最大值
ll ans;      // 最终答案

int ch[MAXNODE]; // ch[t*2+b]：01-Trie 中结点 t 的 b 儿子结点编号，0 表示不存在
int top_node;    // 已用结点的最大编号，1 号是根

// 向 Trie 插入一个前缀异或值 v
void trie_insert(ll v) {
    int t = 1;
    for (int s = bits - 1; s >= 0; --s) {
        int bit = (v >> s) & 1;
        int nxt = ch[t * 2 + bit];
        if (nxt == 0) { // 儿子不存在就新建结点
            ++top_node;
            ch[t * 2 + bit] = top_node;
            nxt = top_node;
        }
        t = nxt;
    }
}

// 在 Trie 已有的前缀异或值里找与 v 异或的最大值
// 贪心：高位收益 2^s 大于所有低位之和，反向儿子存在就走
ll trie_query(ll v) {
    int t = 1;
    ll acc = 0;
    for (int s = bits - 1; s >= 0; --s) {
        int bit = (v >> s) & 1;
        int w = ch[t * 2 + (bit ^ 1)]; // 最想要与当前位相反的儿子
        if (w != 0) {
            acc += 1LL << s;
            t = w;
        } else {
            t = ch[t * 2 + bit];
        }
    }
    return acc;
}

// 求 best[i] = x[1..i] 内所有子数组异或和的最大值，结果存入 best[1..m]
// 依次把前缀异或 P[0..m] 喂给 Trie：先查后插，保证 partner 下标更小、子数组非空
void calc_prefix_best(ll *x, int m, ll *best) {
    // 每次调用复用同一棵 Trie，只清空上次实际用到的结点区域：
    // 结点编号上界是 1 + (m+1)*bits，而 ch 槽位下标最大是结点号的 2 倍多
    memset(ch, 0, sizeof(int) * (2LL * ((m + 1) * bits + 2) + 2));
    top_node = 1;
    pre = 0;
    trie_insert(pre); // 先插入 P[0] = 0
    best[0] = 0;
    for (int i = 1; i <= m; ++i) {
        pre ^= x[i];
        ll h = trie_query(pre); // 以 i 结尾的最大子数组异或 = P[i] 与更早前缀的最大异或
        if (h > best[i - 1]) {
            best[i] = h;
        } else {
            best[i] = best[i - 1]; // 维护前缀最大值
        }
        trie_insert(pre);
    }
}

int main() {
    scanf("%d", &n);
    ll maxv = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        if (a[i] > maxv) maxv = a[i];
    }
    bits = 1;
    while ((1LL << bits) <= maxv) ++bits; // bit_length(max A)，至少为 1

    calc_prefix_best(a, n, f); // f[k]：前 k 个数里的最大子数组异或
    for (int i = 1; i <= n; ++i) b[i] = a[n + 1 - i]; // 反转数组
    calc_prefix_best(b, n, g); // 反转后 g[i] 存的是 b[1..i] 的答案
    for (int i = 1; i <= n / 2; ++i) { // 原地反转只扫前半，避免交换两遍写回原值
        ll t = g[i]; g[i] = g[n + 1 - i]; g[n + 1 - i] = t;
    } // 现在g[k] = A[k..n] 的答案

    ans = 0;
    for (int k = 1; k < n; ++k) { // 枚举分割点：左段在 A[1..k]，右段在 A[k+1..n]
        if (f[k] + g[k + 1] > ans) ans = f[k] + g[k + 1];
    }
    printf("%lld\n", ans);
    return 0;
}

prefix_best 写成生成器逐个产出 $f(k)$ ，不落整张表；Trie 用 array('i') 平坦存储两个儿子槽并按需扩容，避免 Python 对象开销撑爆 128MB 内存；solve 中右半 $g$ 先物化成数组，左半 $f$ 边生成边与 $g(k+1)$ 相加取最大。

复杂度

时间复杂度： $O(N \cdot B)$ ， $B = \mathrm{bit\_length}(\max A) \leqslant 30$ （真实数据 $B=18$ ）。两遍 prefix_best，每遍 $N{+}1$ 个前缀各做一次 $O(B)$ 查询加一次 $O(B)$ 插入，合计约 $4NB$ 层操作， $N = 4 \times 10^5$ 、 $B = 18$ 时约 $2.9 \times 10^7$ 层。与 C++ 正解（同样前缀异或 + 01-Trie）同阶。
空间复杂度： $O(N \cdot B)$ ，Trie 结点数不超过 $1 + (N{+}1)B$ ；array('i') 每结点两槽各 4 字节，按需扩容，实测峰值不超过 128MB。
实测：数据仓全部 10 组真实数据（ $N$ 从 $10^4$ 到 $4 \times 10^5$ ）输出全部一致，单组最大用时约 4.2s（本地限时 20s）。OJ 限时 1s，Python 有 TLE 风险，属 python-oj-short 允许范围；算法复杂度与标准 C++ 正解同阶，不是暴力。

总结

两段不相交 $\Rightarrow$ 枚举分割点 $k$ ：答案 $= \max_k f(k) + g(k+1)$ ，把"段对组合"（ $\Theta(N^4)$ ）拆成前后缀各自的单段极值加一次线性扫描。
子数组异或 $=$ 两个前缀异或之异或： $\mathrm{xor}(A[l..r]) = P_r \oplus P_{l-1}$ ，“以 $r$ 结尾的最大子数组异或"化为" $P_r$ 与历史前缀集合的最大异或”。
01-Trie 逐位贪心：第 $s$ 位收益 $2^s$ 大于所有低位之和，反向儿子存在就走；先查后插保证 partner 下标更小、子数组非空。
$g$ 与 $f$ 同构，反转数组复用同一函数；边界：全零数组 $B=1$ 时 Trie 退化为一层仍正确，重复前缀异或共用路径不影响"存在性"判断。

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

目录

形式化题目

正解

思路

代码

复杂度

总结