菜王的 blog

不用性质的，好写的。

看到 $\textrm{MEX}$ 和 $\textrm{XOR}$ 这两种很难维护的东西出现在一起，又结合 $n \le 5 \times 10^3$ 的数据范围，考虑 DP。

暴力 DP，设状态 $f_{i, j}$ 表示前 $i$ 个数凑出异或和为 $j$ 是否可行，转移暴力转移即可做到 $O(n^3)$。

考虑优化，发现 $f$ 数组对于一个固定的 $j$，满足 $f_{i, j} = 1$ 的 $i$ 是一个后缀。则设 $g_i$ 表示能造出异或和为 $i$ 的最小前缀，转移考虑暴力枚举新区间 $(j, k)$（$g_i < j \le k \le n$）并更新到新的异或和，但是这也是 $O(n^3)$ 的。

接下来可以发现，有多个异或和相同的区间的时候，取右端点最小的即可，所以我们只需要 $O(n^2)$ 预处理出每个区间的 $\textrm{MEX}$，并求出 $to_{l, x}$ 表示 $l$ 后面异或和等于 $x$ 的区间的最小右端点（不存在即为 $n + 1$），求一个后缀 $\min$ 即可。

现在转移 $g_i$ 的时候就只需要枚举新的区间的异或和 $x$，并更新 $g_{i \oplus x} \gets to_{g_i, x}$。关于转移顺序的问题，类似最短路转移一下即可。

代码