# 纳米电脑主机：题解

## 解法比较

出题人解法的线段树按每一位维护区间整体异或、前缀异或为零和为一的数量，以及子区间异或和。拼接时，右区间前缀要按左区间整体异或翻转；跨边界子区间由左右前缀配对计数。下文的前缀异或恒等式和合并证明适用于出题人解法。

Codex（GPT-6）采用的实现只保存长度与一的数量，用长度推出零的数量，并在迭代查询中分别累计左、右摘要以保持拼接顺序。设位数为 $B$ 、操作数为 $q$ ，两者时间均为 $O(nB+qB\log(n+1))$ ，空间为 $O(nB)$ .收益是减少冗余字段、明确非交换合并次序，两种摘要使用同一前缀异或原理。

## 前缀异或

设初始值和所有赋值的非负整数上界为 $U$ ，所需二进制位数为 $B=\max\{1,\lceil\log_2(U+1)\rceil\}$ .所有前缀异或也只需这 $B$ 位表示。

对一个查询区间，设局部前缀异或为 $p_0=0,p_1,\ldots,p_k$ .子区间异或等于两个不同下标的前缀异或之异或，每对前缀唯一对应一个非空子区间。

对二进制位 $b$ ，设这 $k+1$ 个前缀中有 $o_b$ 个为 $1$ ，其余 $k+1-o_b$ 个为 $0$ .异或后该位为 $1$ 的前缀对数为 $o_b(k+1-o_b)$ ，因此答案为

$$\sum_{b=0}^{B-1}2^b o_b(k+1-o_b)$$

## 可合并的区间信息

线段树节点维护区间长度 $k$ 、整个区间的异或值 $z$ ，以及每一位上非空前缀异或为 $1$ 的数量 $o_b$ .合并左区间 L 和右区间 R 时：

- 长度相加，整段异或为 $z_L\oplus z_R$ .
- 左侧前缀不变。右侧每个非空前缀要先异或整个左区间；若 $z_L$ 的第 $b$ 位为 $1$ ，右侧这一位的零和一交换。

所以合并后的一计数为

$$o_b=o_{L,b}+\begin{cases}o_{R,b},&z_L\text{ 的第 }b\text{ 位为 }0\\k_R-o_{R,b},&z_L\text{ 的第 }b\text{ 位为 }1\end{cases}$$

空前缀不在节点内重复保存；查询得到整段信息后，用公式中的 $k+1-o_b$ 把它加入零计数。

## 正确性与实现

合并公式枚举了所有非空前缀：它们要么完全位于左区间，要么由整个左区间接上右侧非空前缀。因此节点信息正确。单点赋值更新叶节点并重新合并；查询按从左到右顺序合并所覆盖的节点，就能得到查询区间的准确前缀计数。前缀对公式随即给出每个子区间的异或值总和。

参考程序使用迭代线段树，查询有左右两个累积结果，分别按正确的拼接方向合并。该合并不满足交换律，不能随意改变顺序。

本题允许取到上界 $U=65536=2^{16}$ ，因此参考程序维护 $B=17$ 位。答案使用 64 位整数。

## 复杂度

每次合并需要遍历 $B$ 个二进制位，耗时 $O(B)$ .建树时间为 $O(nB)$ ，每次单点赋值或区间查询的时间为 $O(B\log n)$ ，空间复杂度为 $O(nB)$ .