最大异或和

GitHub跳转原题关系图返回列表

把后缀异或改写为前缀异或区间查询，用可持久化 01-Trie 支持追加与最大异或。

OJ: luogu

题目 ID: P4735

难度:省选/NOI-

标签:可持久化Trie前缀异或在线追加python

日期: 2026-07-16 19:57

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

序列支持末尾追加。询问在 l <= p <= r 中最大化 a[p] ^ ... ^ a[N] ^ x。

思路

令 s[i] 为前 i 项异或，则询问式为：

text
s[p-1] ^ (s[N] ^ x)

所以要在前缀下标 [l-1,r-1] 中找与固定值异或最大的 s。每加入一个前缀异或，就从旧根复制 24 层路径得到新版本；未修改的子树直接共享。

约定 roots[t] 包含前缀下标 0..t-1。因此查询区间使用 roots[r] - roots[l-1] 的节点计数差。每一位优先进入能让异或位为 1 且差分计数大于 0 的儿子。

Python 知识

  • operation = input().split() 保留首项为 bytes，可直接与 b"A" 比较。
  • clone 同步复制三个紧凑数组中的一个节点。
  • array("i") 的节点下标和计数足够容纳约 1500 万节点，内存远低于嵌套列表对象。
  • 当前总前缀异或只需一个整数变量随追加更新。

代码

python
import sys
from array import array


MAX_BIT = 23
input = sys.stdin.buffer.readline
n, operation_count = map(int, input().split())
initial = map(int, input().split())
left = array("i", [0])
right = array("i", [0])
count = array("i", [0])


def clone(node):
    left.append(left[node])
    right.append(right[node])
    count.append(count[node])
    return len(count) - 1


def insert(previous_root, value):
    root = clone(previous_root)
    count[root] += 1
    previous, current = previous_root, root
    for bit in range(MAX_BIT, -1, -1):
        if value >> bit & 1:
            child = clone(right[previous])
            right[current] = child
            previous = right[previous]
        else:
            child = clone(left[previous])
            left[current] = child
            previous = left[previous]
        current = child
        count[current] += 1
    return root


def maximum_xor(older_root, newer_root, value):
    answer = 0
    for bit in range(MAX_BIT, -1, -1):
        if value >> bit & 1:
            wanted_old, wanted_new = left[older_root], left[newer_root]
            other_old, other_new = right[older_root], right[newer_root]
        else:
            wanted_old, wanted_new = right[older_root], right[newer_root]
            other_old, other_new = left[older_root], left[newer_root]
        if count[wanted_new] > count[wanted_old]:
            answer |= 1 << bit
            older_root, newer_root = wanted_old, wanted_new
        else:
            older_root, newer_root = other_old, other_new
    return answer


roots = array("i", [0])
prefix_xor = 0
roots.append(insert(0, 0))
for value in initial:
    prefix_xor ^= value
    roots.append(insert(roots[-1], prefix_xor))

answers = []
for _ in range(operation_count):
    operation = input().split()
    if operation[0] == b"A":
        prefix_xor ^= int(operation[1])
        roots.append(insert(roots[-1], prefix_xor))
    else:
        left_index, right_index, value = map(int, operation[1:])
        value ^= prefix_xor
        answers.append(str(maximum_xor(roots[left_index - 1], roots[right_index], value)))

print("\n".join(answers))

复杂度

每次追加和询问都处理 24 位，时间 O((n+m)⋅24)O((n+m)\cdot24)；每次追加新建 25 个节点，空间 O((n+m)⋅24)O((n+m)\cdot24)。

总结

先把后缀式改写成前缀异或，再用版本差表达下标范围，是可持久化 01-Trie 的标准模型。