科尔涅耶维奇与异或（困难版）题解

思路

对每个异或值 $z$，维护产生 $z$ 的严格递增子序列中最小的末尾元素 $last_z$。空子序列令 $last_0=-1$。读到值 $v$ 时，所有满足 $last_z<v$ 的状态都可转移到 $z\mathbin{\mathtt{xor}}v$，并把新状态末尾更新为 $v$。

做法

子任务 1 枚举全部子序列并检查严格递增。

子任务 2 对每个输入元素扫描全部 $8192$ 个异或状态，复杂度 $O(8192n)$。

满分算法利用 $0\le v\le5000$。当某个 $last_z$ 从旧值降到新值时，状态 $z$ 只会新获得阈值 $v\in(new,old]$ 的转移资格，把 $z$ 加入这些值的待处理表。输入出现 $v$ 时只处理尚未为该 $v$ 使用过的状态。每个二元组 $(v,z)$ 最多处理一次。

正确性证明

若存在异或为 $z$、末尾小于 $v$ 的递增子序列，则追加当前 $v$ 后得到异或 $z\mathbin{\mathtt{xor}}v$ 的合法子序列；反之任何以当前 $v$ 结尾的合法子序列删去末项后必来自这样的状态。只保留最小末尾不会损失任何后续转移。待处理表恰在最小末尾首次低于阈值时加入状态，且每个阈值状态对只处理一次，因此优化与逐元素扫描完全等价。

复杂度

时间复杂度 $O(n+5001\times8192)$，空间复杂度 $O(5001\times8192)$。