UOJ Round #22
A. 月球列车
30
$n, m \le 10^3$
暴力模拟。
时间复杂度 $\mathcal O(n m)$。
60
$n, m \le 10^5$
对于一次查询 $x$，依次考虑每一个二进制位是 $0$ 还是 $1$。
设 $a’{j,i} = a_i \& (2^{j + 1} - 1)$，对于每个 $i$，$a_i + x$ 的 $2^j$ 位是 $a_i \oplus x$ 的 $2^j$ 位再异或上 $a_i + x$ 的第 $j - 1$ 位是否进位，前者容易处理，后者等价于 $a’{j - 1, i} + (x \& (2^j - 1)) \ge 2^j$，所以求 $\bigoplus \limits_{i = 1}^n (a_i + x)$ 的 $2^j$ 位时只需求出有多少个 $a’_{j - 1,i} \ge 2^j - (x \& (2^j - 1))$，可以排序预处理后对每一位二分。
时间复杂度 $\mathcal O((n + m) \log n\log a_i)$。
90
$n, m \le 2.5 \times 10^5$
$t = 0$
排序预处理的部分可以利用上一次排序的结果，将新的一位为 $0$ 的部分和为 $1$ 的部分归并排序，使预处理复杂度降至 $\mathcal O(n \log a_i)$。
将查询离线，同样可以按上述方法将 $x$ 的前 $j - 1$ 位的顺序用 $\mathcal O(m \log a_i)$ 的复杂度求出，然后对于每一位，线性 Two Pointers 求出每个查询在这一位上的答案。
时间复杂度 $\mathcal O((n + m) \log a_i)$。
B. 月球铁轨
10
$n \le 10^3$
定义 $f(x, T) = \max_{y \in T} (x \oplus y), g(x, T) = \min_{y \in T} (x \oplus y)$，其中 $x$ 是一个数，$T$ 是一个 $\mathbb{F}_2$ 上的线性空间。
令 $c_i = a_i \oplus b_i(1 \le i \le n)$，对于区间 $[l, r]$，求出 $x_{l, r} = \oplus_{i = l}^{r} a_i$，再对 $c_l \cdots c_r$ 求出张出的线性空间 $T_{l, r}$，则答案为 $f(x_{l, r}, T_{l, r})$。
维护线性空间（可以维护一组基）以及求出 $f(x_{l, r}, T_{l, r})$ 的复杂度均为 $\mathcal O(m)$。
时间复杂度 $\mathcal O(n^2 m)$。
25
$a_i, b_i$（$1 \le i \le n$）均在 $[0, 2^m)$ 范围内独立等概率随机。
如果一个区间的线性空间维数达到 $m$，这个区间的答案就是 $2^m - 1$。
随机数据下，维数小于 $m$ 的区间只有 $\mathcal O(n m)$ 个，求出这些区间的答案后使用经典算法求出第 $k$ 小。
时间复杂度 $\mathcal O(n m^2)$。
40
$a_i = b_i$（$1 \le i \le n$）。
定义 $S_n = \oplus_{i = 1}^n a_i$，则 $x_{l, r} = S_r \oplus S_{l - 1}$。
一个区间的答案是 $S_r \oplus S_{l - 1}$，于是把所有前缀异或和插入一颗 TTie，然后 Trie 上二分即可求出第 $k$ 小的答案。
时间复杂度 $\mathcal O(n m)$。
55
$a_i = 0$（$1 \le i \le n$）
区间 $[l, r]$ 答案是 $f(0, T_{l, r})$。
对于某个固定的 $l$，$T_{l, r}$ 最多只有 $m + 1$ 种，维数分别为 $0 \sim m$，并且如果区间 $A$ 包含区间 $B$，$T_A$ 包含 $T_B$。
使用扫描线算法，每次在序列末尾加入一个数 $S_r$，并且维护出每个左端点当前对应的线性空间。
加入一个数会使当前一个后缀的线性空间维数变大 $1$，维数变大总次数是 $\mathcal O(n m)$ 的，暴力维护即可。
时间复杂度 $\mathcal O(n m^2)$。
C. 月球车站
5
$a = 0$
伏特永远不会翻转，因此当且仅当初始硬币全为正面，答案为 0，否则 skip 蚤也选择不操作答案为 -1。
15
$b = 0$
伏特每次遇到背面的硬币都会将它翻转。
把同色的连续一些硬币称为一段。对于段数大于 $2$ 的局面，skip 蚤也只需要每次遇到正面的硬币都将它反转即可，容易发现这样即可让游戏无法结束。
当局面为全 0 或全 1，伏特显然获胜。
当局面为 00...011...1 时，显然伏特会获胜。
当局面为 11...100...0 时，伏特能否获胜与 1 的个数有关。
当仅有一个 1 时，不管 skip 蚤如何操作，都会变为上述伏特必胜局面，否则，skip 蚤不翻转第一个 1 ，即可使段数大于 $2$，于是游戏无法结束。
判断一下即可。