分割、异或与征服题解

思路

称一个区间合法，当且仅当它能从初始区间通过若干次操作得到。直接记录全部合法区间并枚举分割点可以做到三次复杂度。满分做法需要把“存在某个更大合法区间”的信息压缩下来。

考虑从合法区间 $[l,R]$ 保留左半部分 $[l,r]$。令 $A$ 为 $[l,r]$ 的异或和，$B$ 为 $[r+1,R]$ 的异或和，$T=A\mathbin\oplus B$ 为整个区间的异或和。

若 $T=0$，则 $A=B$，可以任选一边保留。否则，$A$ 与 $B$ 从高到低第一个不同的二进制位正是 $T$ 的最高位；能够保留左边，当且仅当 $A$ 在这一位为 $1$。保留右边的条件完全对称。

做法

预处理异或前缀和，从而常数时间求任意区间异或和。

对每个左端点 $l$ 维护位掩码 $L_l$。若某个已经确认合法的区间 $[l,R]$ 的异或和最高位为 $b$，就在 $L_l$ 中记录第 $b$ 位。若该异或和为零，则记录一个额外的哨兵位，表示从这个合法区间可以无条件保留任意左前缀。

类似地，对每个右端点 $r$ 维护掩码 $R_r$。

按照区间长度从大到小枚举 $[l,r]$。初始的 $[1,n]$ 合法。对于其他区间，设其异或和为 $x$，并在 $x$ 上补上哨兵位。若

$$(x\mathbin\&L_l)\ne0 \quad\text{或}\quad (x\mathbin\&R_r)\ne0,$$

则该区间可以从某个更大的合法区间得到。确认合法后，把 $x$ 的最高位或零异或哨兵加入对应的两个端点掩码。长度为一的合法区间就是最终可以留下的位置。

第一档可以对每个目标位置递归枚举所有操作序列。第二档显式记录所有可达区间，并从每个可达区间枚举分割点向更短区间转移。

正确性证明

对任意分割，若整个区间异或和 $T$ 非零，则 $T$ 的最高位正是两部分异或和 $A,B$ 的最高不同位。因此在该位为 $1$ 的一边数值更大，并且只有这一边能被保留。若 $T=0$，则 $A=B$，两边都能保留。这证明端点掩码记录的每一位恰好描述一种可行的扩展来源。

按长度递减处理时，掩码中只包含已经证明合法且严格更长的区间信息。若当前异或和与某个记录位相交，依据上一段的比较结论，当前区间能从相应的大区间一步得到，所以转移充分。反之，当前区间若可由某个更大合法区间一步得到，该大区间的最高异或位或零哨兵已经写入相同端点的掩码，而当前区间异或和必然满足对应位条件，所以转移也必要。

由区间长度递减归纳，算法判定的合法区间集合与真实可达区间集合完全相同，最终输出的单点状态因此正确。

复杂度

每个测试用例枚举 $O(n^2)$ 个区间，每个区间做常数次位运算，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。