可持久化 01-Trie 求每个右端点的第 r 大子数组异或，用堆归并取全局前 k 大。
OJ: luogu
题目 ID: P5283
难度:省选/NOI-
标签:可持久化Trie异或堆前k大python
日期: 2026-07-16 19:57
题意
每个非空连续区间产生一个区间异或值，从所有不同区间中选择 k 个，使异或值之和最大。
思路
设前缀异或为 prefix[i]，区间 [l,r] 的值是 prefix[r] ^ prefix[l-1]。固定右端点 r 后，候选集合就是 prefix[r] 与 prefix[0:r] 中每个值的异或。
建立前缀异或的可持久化 01-Trie，roots[r] 恰好包含 prefix[0] 到 prefix[r-1]。沿位从高到低，根据子树计数即可求固定右端点的第 rank 大异或。
每个右端点形成一个递减候选序列。先把每列第 1 大放入最大堆；弹出一项后，只把同一列第 2、3……大依次补入。弹 k 次就是全局前 k 大的和。
Python 知识
heapq是小根堆，存负值即可模拟最大堆。- 堆元素
(-value, end, rank)同时记录来源列与下一排名。 - 三个
array("i")保存左右儿子和节点计数，避免上千万节点对象。 array("I")保存 32 位无符号前缀异或。
代码
python
import heapq
import sys
from array import array
MAX_BIT = 31
input = sys.stdin.buffer.readline
n, required = map(int, input().split())
values = 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 kth_xor(root, value, rank):
answer = 0
for bit in range(MAX_BIT, -1, -1):
wanted = left[root] if value >> bit & 1 else right[root]
wanted_count = count[wanted]
if rank <= wanted_count:
answer |= 1 << bit
root = wanted
else:
rank -= wanted_count
root = right[root] if value >> bit & 1 else left[root]
return answer
prefix_xor = array("I", [0])
for value in values:
prefix_xor.append(prefix_xor[-1] ^ value)
roots = array("i", [0, insert(0, 0)])
for value in prefix_xor[1:]:
roots.append(insert(roots[-1], value))
heap = [(-kth_xor(roots[end], prefix_xor[end], 1), end, 1)
for end in range(1, n + 1)]
heapq.heapify(heap)
answer = 0
for _ in range(required):
negative, end, rank = heapq.heappop(heap)
answer -= negative
if rank < end:
rank += 1
heapq.heappush(heap, (-kth_xor(roots[end], prefix_xor[end], rank), end, rank))
print(answer)复杂度
Trie 建立 rank 大查询
总结
“每个右端点一列有序候选 + 堆归并”把无法枚举的 k 个需要的值。