Fotile模拟赛L

形式化题目

给定长为 $N$ 的序列 $A_1, \dots, A_N$ 与 $M$ 组询问。每组询问给出区间 $[l, r]$ ，要求该区间内连续非空子段的最大异或和：

\max_{l \leqslant i \leqslant j \leqslant r}\ A_i \oplus A_{i+1} \oplus \cdots \oplus A_j.

询问在线给出：由输入对 $(x, y)$ 与上一问答案 $lastans$ （初始 $0$ ）解码，两项分别取 $(x+lastans) \bmod N + 1$ 与 $(y+lastans) \bmod N + 1$ ，小者为 $l$ 、大者为 $r$ 。 $N = 12000$ ， $M = 6000$ ， $0 < x, y, A_i < 2^{31}$ 。

样例的解码链与答案（ $A = [1, 4, 3]$ ，前缀异或 $S = [0, 1, 5, 6]$ ）：

询问	x	y	进入时 lastans	解码两项	区间	最优子段	答案
1	0	1	0	1, 2	$[1, 2]$	$1 \oplus 4$	5
2	0	1	5	3, 1	$[1, 3]$	$4 \oplus 3$	7
3	4	3	7	3, 2	$[2, 3]$	$4 \oplus 3$	7

"解码两项"是取 min/max 之前的两个数。观察两点： $lastans$ 沿询问链传递，第 2 问被第 1 问的答案平移到 $[1, 3]$ ；最优子段未必铺满区间——第 2 问区间是 $[1, 3]$ ，取到的却是其中的 $[2, 3]$ ，这正说明答案要在 $O(N^2)$ 个子段里挑，不能只比较整个区间。

正解

思路

从朴素枚举说起。 对每个询问枚举全部 $(i, j)$ 逐段求异或和是 $O(M N^2)$ ；即使先记前缀异或、把"算一段"降到 $O(1)$ ，枚举下标对仍是每问 $O(N^2)$ 。真正的瓶颈是：两个下标都要落在 $[l, r]$ 内，候选集合随询问变化，没法一次预处理包办。

记 $S_k = A_1 \oplus \cdots \oplus A_k$ （ $S_0 = 0$ ），则子段 $A_i \cdots A_j$ 的异或和 $= S_{i-1} \oplus S_j$ 。先解决一半：若右端点 $q$ 固定、左端点只能在任意区间 $[lo, hi]$ 里挑，就是经典 01 Trie 贪心——从第 30 位到第 0 位，只要区间里存在走反方向（让该位为 1）的数就走反方向， $O(31)$ 。

把"区间"做进 Trie：可持久化。 按 $k = 0, 1, \dots, N$ 依次插入 $S_k$ ，每插一次保存根，得到一列版本；插入只复制路径上的节点、其余共享。查询 $\max_{q \in [lo, hi]} S_q \oplus x$ 时拿"插到 $hi$ "与"插到 $lo-1$ "两个版本的根同时下钻：同一路径位置两节点的子树计数差恰好是区间 $[lo, hi]$ 内走到这里的元素个数，计数差大于 $0$ 就说明能走反方向。于是任意区间、任意 $x$ 的最大异或都能 $O(31)$ 回答——这就是代码里的 range_max_xor(hi, lo, x)。

再用分块消掉另一端的枚举。 一次询问 $p = i-1$ 、 $q = j$ 两端都被 $[l, r]$ 包住，只靠上面对 $[lo, hi]$ 的查询仍要枚举另一端 $O(N)$ 。设块长 $B \approx \sqrt N$ ， $L$ 为 $l$ 所在块的末尾，把 $[l, r]$ 内的子段按端点位置分成三类（ $l, r$ 同块时没有完整块，直接枚举右端点 $j$ ，每次问"候选左端点集合 $S_{[l-1, j-1]}$ 与 $S_j$ 的最大异或"， $O(B \times 31)$ ）；下图是三类子段与对应查询手段的对应关系：

graph TD
    Q["询问 [l, r]，l、r 不同块，L 为 l 所在块末尾"] --> C1["第一类：两端都在左段 [l, L]"]
    Q --> C2["第二类：起点在左段，终点 >= L+1"]
    Q --> C3["第三类：起点 >= L+1，终点 <= r"]
    C1 --> A1["查预处理 g[l]，O(1)"]
    C2 --> A2["枚举 <= B 个起点，各做一次区间查询，O(B*31)"]
    C3 --> A3["查预处理 f[块(l)+1][r]，O(1)"]

三类互斥且合并恰好覆盖所有合法子段：终点不超过 $L$ 的子段两端必然都在 $[l, L]$ （第一类）；终点越过 $L$ 后，起点在左段归第二类、起点也在 $L+1$ 之后归第三类。逐类落实：

第一类：预处理 $g[i]$ = " $i$ 到所在块末尾"的最大子段异或。每块内从右往左扫，维护"起点固定在 $i-1$ 、终点在 $[i, \text{块末}]$ "的区间查询最大值并与右邻答案取 max，全程只花 $N$ 次查询，询问时 $O(1)$ 取 $g[l]$ 。
第二类： $p = i-1$ 只在 $[l-1, L-1]$ ，至多 $B$ 个；对每个 $p$ 在固定区间 $S_{[L+1, r]}$ 上做一次 range_max_xor，共 $O(B \times 31)$ 。恒有 $p < q$ ，不会取到空子段。
第三类：预处理 $f[\text{块}][j]$ = "起点不早于该块首、终点不超过 $j$ "的最大子段异或。对每个块首向右扫描、边扫边保留历史最大，询问时直接 $O(1)$ 取 $f[\text{块}(l)+1][r]$ ； $l$ 的下一个块首之前的起点已被第二类覆盖，此处起点从 $L+1$ 数起不重不漏。

块长平衡。 预处理 $f$ 约 $N^2/(2B)$ 次查询、单次询问至多约 $B$ 次查询，总代价 $N^2/(2B) + M \cdot B$ 在 $B \approx N/\sqrt{2M} \approx 110 \approx \sqrt N$ 处平衡，代码取 block = int(n ** 0.5)。询问虽在线，但解码只依赖上一问的答案，按输入顺序处理、维护 last（即 lastans）即可，与结构无关。

代码

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 区间最大异或和：可持久化 01 Trie + 分块预处理（块内右端固定、左端固定的最优值）。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

typedef long long ll;

const ll MAX_BIT = 30; // Ai < 2^31
const ll MAXNODE = 500000;

ll CNT[MAXNODE]; // 子树计数
ll CH0[MAXNODE];
ll CH1[MAXNODE];
std::vector<ll> RO; // RO[k] = 插入 S[0..k-1] 之后的根

ll node_cnt = 1; // 0 号是空版本

// 把前缀异或 x 插入 Trie，沿路复制出一个新版本并返回新版本的根
ll trie_extend(ll prev, ll x) {
    ll root = node_cnt++;
    CNT[root] = CNT[prev] + 1;
    CH0[root] = CH0[prev]; // 没走到的另一支原样共享
    CH1[root] = CH1[prev];
    ll cur = root, old = prev;
    for (ll k = MAX_BIT; k >= 0; k--) {
        ll bit = (x >> k) & 1;
        ll old_child = bit ? CH1[old] : CH0[old];
        ll nx = node_cnt++;
        CNT[nx] = CNT[old_child] + 1;
        CH0[nx] = CH0[old_child];
        CH1[nx] = CH1[old_child];
        if (bit == 0) CH0[cur] = nx;
        else CH1[cur] = nx;
        cur = nx;
        old = old_child;
    }
    return root;
}

// 前缀异或区间 S[lo..hi] 中，与 x 异或的最大值
ll range_max_xor(ll hi, ll lo, ll x) {
    ll u = RO[hi + 1], v = RO[lo]; // v 是 lo 之前的版本，作差得到区间
    ll best = 0;
    for (ll k = MAX_BIT; k >= 0; k--) {
        ll bit = (x >> k) & 1;
        if (bit) { // 想让结果这一位为 1 就走反方向 0
            ll pu = CH0[u], pv = CH0[v];
            if (CNT[pu] > CNT[pv]) {
                best |= 1LL << k;
                u = pu; v = pv;
            } else {
                u = CH1[u]; v = CH1[v];
            }
        } else { // 想走反方向 1
            ll pu = CH1[u], pv = CH1[v];
            if (CNT[pu] > CNT[pv]) {
                best |= 1LL << k;
                u = pu; v = pv;
            } else {
                u = CH0[u]; v = CH0[v];
            }
        }
    }
    return best;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    std::vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    // 前缀异或 S[i] = A1 xor ... xor Ai，子段异或和 = S[i-1] xor S[j]
    std::vector<ll> s(n + 1, 0);
    for (ll i = 1; i <= n; i++) {
        s[i] = s[i - 1] ^ a[i - 1];
    }

    RO.assign(n + 2, 0); // RO[0] 是空版本，RO[k+1] = 插入 S[0..k] 之后的根
    for (ll k = 0; k <= n; k++) {
        RO[k + 1] = trie_extend(RO[k], s[k]);
    }

    ll block = (ll)std::sqrt((double)n); // 块长 ~sqrt(N)
    if (block < 1) block = 1;
    ll block_count = (n + block - 1) / block;

    std::vector<ll> g(n + 1, 0); // g[i]：从 i 到所在块末尾的最大子段异或和
    for (ll start = 0; start < n; start += block) {
        ll block_lo = start + 1;
        ll block_hi = start + block;
        if (block_hi > n) block_hi = n;
        ll best = 0;
        for (ll i = block_hi; i >= block_lo; i--) {
            ll cand = range_max_xor(block_hi, i, s[i - 1]);
            if (cand > best) best = cand;
            g[i] = best;
        }
    }

    // f[bi][j - base]：起点 >= bi*block+1 且终点 <= j 的最大子段异或和
    std::vector<std::vector<ll> > f(block_count + 1);
    for (ll bi = 1; bi < block_count; bi++) {
        ll base = bi * block + 1;
        f[bi].assign(n + 2, 0);
        ll best = 0;
        for (ll j = base; j <= n; j++) {
            ll cand = range_max_xor(j - 1, base - 1, s[j]);
            if (cand > best) best = cand;
            f[bi][j] = best;
        }
    }

    ll last = 0; // 在线询问：上一问的答案参与下一问的解码
    for (ll q = 0; q < m; q++) {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        ll p = (x + last) % n + 1, qq = (y + last) % n + 1;
        ll l = p, r = qq;
        if (l > r) {
            ll t = l; l = r; r = t;
        }
        ll left_block = (l - 1) / block, right_block = (r - 1) / block;
        ll best;
        if (left_block == right_block) { // 同块：右端点最多扫一个块
            best = 0;
            for (ll j = l; j <= r; j++) {
                ll cand = range_max_xor(j - 1, l - 1, s[j]);
                if (cand > best) best = cand;
            }
        } else {
            ll left_end = (left_block + 1) * block; // 左段末尾，一定 < r
            // 三段覆盖 [l, r] 内所有子段：左段内 / 跨过左段 / 从第一个完整块起
            ll across = 0;
            for (ll t = l - 1; t < left_end; t++) {
                ll cand = range_max_xor(r, left_end + 1, s[t]);
                if (cand > across) across = cand;
            }
            best = g[l];
            if (across > best) best = across;
            ll third = f[left_block + 1][r];
            if (third > best) best = third;
        }
        last = best;
        printf("%lld\n", last);
    }
    return 0;
}

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
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140#!/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-10-01 20:22
# update_at: 2026-10-01 20:22

import sys

MAX_BIT = 30  # Ai < 2^31，前缀异或的最高有效位是第 30 位

# 可持久化 01 Trie：节点 0 是空版本，CNT 是子树计数，CH0/CH1 是两个孩子编号
CNT: list[int] = [0]
CH0: list[int] = [0]
CH1: list[int] = [0]
RO: list[int] = [0]  # RO[k] = 插入 S[0..k-1] 之后的根；RO[0] 是空版本


def trie_extend(prev: int, x: int) -> int:
    """把前缀异或 x 插入 Trie，沿路复制出一个新版本并返回新版本的根。

    版本只增不删，所以同一位置的节点在两个版本里的计数差，
    就是两个版本之间插入的数在该分支上的个数。
    """
    root = len(CNT)
    CNT.append(CNT[prev] + 1)
    CH0.append(CH0[prev])  # 没走到的另一支原样共享
    CH1.append(CH1[prev])
    new_node, old_node = root, prev
    for k in range(MAX_BIT, -1, -1):
        bit = x >> k & 1
        old_child = CH0[old_node] if bit == 0 else CH1[old_node]
        node = len(CNT)
        CNT.append(CNT[old_child] + 1)          # 旧分支上的计数 + 本次插入
        CH0.append(CH0[old_child])              # 沿路复制，没走到的另一支原样共享
        CH1.append(CH1[old_child])
        if bit == 0:
            CH0[new_node] = node
        else:
            CH1[new_node] = node
        new_node, old_node = node, old_child
    return root


def range_max_xor(
    hi: int,
    lo: int,
    x: int,
    ro: list[int] = RO,
    cnt: list[int] = CNT,
    ch0: list[int] = CH0,
    ch1: list[int] = CH1,
) -> int:
    """前缀异或区间 S[lo..hi] 中，与 x 异或的最大值。

    两个版本根同时下钻：某分支的计数差大于 0 说明区间里有人走过，
    就贪心走能使结果这一位为 1 的方向。
    """
    u, v = ro[hi + 1], ro[lo]  # v 是 lo 之前的版本，作差得到区间
    best = 0
    for k in range(MAX_BIT, -1, -1):
        bit = x >> k & 1
        if bit:  # 想让结果这一位为 1 就走反方向 0
            pu, pv = ch0[u], ch0[v]
            if cnt[pu] > cnt[pv]:
                best |= 1 << k
                u, v = pu, pv
            else:
                u, v = ch1[u], ch1[v]
        else:  # 想走反方向 1
            pu, pv = ch1[u], ch1[v]
            if cnt[pu] > cnt[pv]:
                best |= 1 << k
                u, v = pu, pv
            else:
                u, v = ch0[u], ch0[v]
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)
    a = [next(data) for _ in range(n)]

    # 前缀异或 S[i] = A1 xor ... xor Ai，子段异或和 = S[i-1] xor S[j]
    s = [0] * (n + 1)
    for i in range(1, n + 1):
        s[i] = s[i - 1] ^ a[i - 1]

    for k in range(n + 1):  # 建 n+1 个版本，之后任意前缀区间都能两版本作差
        RO.append(trie_extend(RO[-1], s[k]))

    block = max(1, int(n ** 0.5))  # 块长 ~sqrt(N)：预处理 N^1.5、单次询问 N^0.5
    block_count = (n + block - 1) // block

    # g[i]：从 i 到所在块末尾的最大子段异或和，供询问左段 O(1) 取用
    g = [0] * (n + 1)
    for start in range(0, n, block):
        block_lo, block_hi = start + 1, min(start + block, n)
        best = 0
        for i in range(block_hi, block_lo - 1, -1):
            # 起点固定在 i-1，终点在 [i, 块末尾] 里挑
            best = max(best, range_max_xor(block_hi, i, s[i - 1]))
            g[i] = best

    # f[bi]：起点 >= bi*block+1 且终点 <= j 的最大子段异或和（base = bi*block+1）
    f: list[list[int]] = [[]]  # f[0] 占位：第一个完整块之前的起点用不上
    for bi in range(1, block_count):
        base = bi * block + 1
        row = [0] * (n - base + 1)
        best = 0
        for j in range(base, n + 1):
            # 终点固定在 j，起点在 [base, j] 里挑（含单元素 A[j]）
            best = max(best, range_max_xor(j - 1, base - 1, s[j]))
            row[j - base] = best
        f.append(row)

    out: list[str] = []
    last = 0  # 在线询问：上一问的答案参与下一问的解码
    for _ in range(m):
        x, y = next(data), next(data)
        p, q = (x + last) % n + 1, (y + last) % n + 1
        l, r = (p, q) if p <= q else (q, p)
        left_block, right_block = (l - 1) // block, (r - 1)// block
        if left_block == right_block:  # 同块：右端点最多扫一个块
            best = max(range_max_xor(j - 1, l - 1, s[j]) for j in range(l, r + 1))
        else:
            left_end = (left_block + 1) * block  # 左段末尾，一定 < r
            # 三段覆盖 [l, r] 内所有子段：左段内 / 跨过左段 / 从第一个完整块起
            across = max(range_max_xor(r, left_end + 1, s[t]) for t in range(l - 1, left_end))
            best = max(g[l], across, f[left_block + 1][r - (left_end + 1)])
        last = best
        out.append(str(best))

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

复杂度

建持久化 Trie： $(N+1)$ 次插入 $\times$ 31 层， $O(N \times 31)$ ；预处理 $g$ 为 $O(N \times 31)$ ，预处理 $f$ 为 $O(N^2 / B \times 31)$ 。
单次询问：同块或跨块都至多枚举一个块 $= O(B \times 31)$ ，两张表查询 $O(1)$ 。
取 $B = \sqrt N$ 后总时间 $O((N+M)\sqrt N \times 31)$ ，与标准 C++ 解法（分块 + 可持久化 Trie）同阶；空间 $O(N \times 31 + N^2/B) = O(N\sqrt N)$ ，Trie 约 $3.8\times10^5$ 个节点、 $f$ 表约 $6.5\times10^5$ 个整数。
实测：10 组真实数据（ $N=12000, M=6000$ ）输出全部一致，单组 3.2~3.6s、峰值约 50MB （本地限时 20s、不设内存硬限制；OJ 的 1000ms 是 C++ 参照，本仓库 Python 解法按约定以输出正确为准）。

总结

答案链条是：子段异或和 $\to$ 前缀异或对 $S_p \oplus S_q$ $\to$ 可持久化 01 Trie 的区间最大异或查询 $\to$ 分块三分 + 两张端点预处理表。持久化 Trie 负责把"一端在任意区间" 压到 $O(31)$ ，分块负责把"另一端只能枚举一个块"，两者拼起来就是预处理 $O(N^{1.5})$ 、单问 $O(\sqrt N)$ 的标准解。实现上最值得记住的不变量：版本只增不删，所以两版本同位置节点的计数差就是区间计数；三类子段覆盖互斥完备，取 max 即为答案。

目录

形式化题目

正解

思路

代码

复杂度

总结