P5283.md

提示 1

求出异或前缀和数组 $s$ 后，问题变成找两数异或最大的 $k$ 对数字。

联想到 373. 查找和最小的 K 对数字，往最大堆 + 0-1 字典树的方面去思考。

提示 2

两个数字 $s[i]$ 和 $s[j]$，如果对于 $s[i]$ 来说，它如果和 $s[j]$ 异或最优，那么对于 $s[j]$ 来说，它也和 $s[i]$ 异或最优。

如果为了避免重复统计，还要考虑下标约束的话，就太困难了。

一个好方法是，改为统计两数异或最大的 $2k$ 对数字。这样对每个 $s[i]$ 而言，就无需考虑下标的约束了，问题变成 $s[i]$ 和 $s$ 的最大异或和、次大异或和、……。

提示 3

用最大堆模拟。堆中维护 $n+1$ 个三元组（因为 $s$ 中有 $n+1$ 个数），每个三元组表示：$s[i]$ 与 $s$ 的第 $x$ 大异或和，$i$，$x$。

一开始 $x$ 均为 $1$。

每次取出堆顶加入答案，然后把 $x$ 加一，算出新的异或和，再入堆。

提示 4

如何计算第 $x$ 大异或和？

和最大异或和一样，从高位往低位思考。如果当前位是 $1$，那么看 $0$ 子树中的叶子个数 $\textit{cnt}$ 是否大于等于 $x$，如果是，那么去 $0$ 子树；否则 $0$ 子树的元素太少，去 $1$ 子树找第 $x-\textit{cnt}$ 大异或和。具体见代码。

package main

import (
	"bufio"
	"container/heap"
	. "fmt"
	"io"
	"os"
	"runtime/debug"
)

func init() { debug.SetGCPercent(-1) }

type trieNode struct {
	son [2]*trieNode
	cnt int32
}

type trie struct{ root *trieNode }

const trieBitLen = 32

func (t *trie) put(v int) *trieNode {
	o := t.root
	for i := trieBitLen - 1; i >= 0; i-- {
		b := v >> i & 1
		if o.son[b] == nil {
			o.son[b] = &trieNode{}
		}
		o = o.son[b]
		o.cnt++
	}
	return o
}

func (t *trie) maxXorKth(v int, k int32) (ans int) {
	o := t.root
	for i := trieBitLen - 1; i >= 0; i-- {
		b := v >> i & 1
		if o.son[b^1] != nil {
			if k <= o.son[b^1].cnt {
				ans |= 1 << i
				b ^= 1
			} else {
				k -= o.son[b^1].cnt
			}
		}
		o = o.son[b]
	}
	return
}

func run(_r io.Reader, out io.Writer) {
	in := bufio.NewReader(_r)
	var n, k, ans int
	Fscan(in, &n, &k)
	a := make([]int, n+1)
	t := &trie{&trieNode{}}
	t.put(0)
	for i := 1; i <= n; i++ {
		Fscan(in, &a[i])
		a[i] ^= a[i-1]
		t.put(a[i])
	}

	h := make(hp, n+1)
	for i, v := range a {
		h[i] = tuple{t.maxXorKth(v, 1), i, 1}
	}
	heap.Init(&h)

	for k *= 2; k > 0; k-- {
		p := &h[0]
		ans += p.xor
		p.k++
		p.xor = t.maxXorKth(a[p.i], p.k)
		heap.Fix(&h, 0)
	}
	Fprint(out, ans/2)
}

func main() { run(os.Stdin, os.Stdout) }
type tuple struct{ xor, i int; k int32 }
type hp []tuple
func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].xor > h[j].xor }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (hp) Push(any)             {}
func (hp) Pop() (_ any)         { return }

时间复杂度：$\mathcal{O}(n \log U + k(\log n+ \log U))$，其中 $U=\max(a)$，本题 $\log U$ 可以视作 $32$。