# 异星工厂：信号网络：两个无符号字

出题人解法：把寄存器作为整数，用循环移位和区间掩码维护；另有循环起点加线段树的程序。Codex（GPT-6）：将整数方案实现为两个标准 64 位无符号字，处理零移位、跨字边界和完整字掩码。

## 表示和取反

用 $L$ 保存第 $0$ 至 $63$ 位，用 $H$ 保存第 $64$ 至 $127$ 位，整体为 $A=L+2^{64}H$ .

令 $P(t)$ 表示低 $t$ 位为一的 64 位掩码。对于 $0\le t<64$ ，它等于 $2^t-1$ ；$P(64)$ 单独返回全一。一个字内的闭区间 $[l,r]$ 掩码为

$$P(r+1)\mathbin{\oplus}P(l)$$

低于 $l$ 的一被异或抵消，留下恰好需要取反的位。跨过字边界时，把区间拆成低字、高字两段，并把高字段下标减去 $64$ .将对应字与掩码异或即可。

## 循环右移

先令 $k=(x\bmod128+128)\bmod128$ .如果 $k\ge64$ ，交换两个字，再令 $k\leftarrow k-64$ .余下 $k=0$ 时结束，否则此时 $1\le k\le63$ ，计算

$$L'=(L\gg k)\mathbin{|}(H\ll(64-k))$$

$$H'=(H\gg k)\mathbin{|}(L\ll(64-k))$$

两个式子都必须读旧值，因此先保存旧低字。每个式子的两部分位段互不重叠：一个字右侧移出的位恰好填入另一个字的高位。交换两字就是旋转半个寄存器，与余下旋转合成所需结果。

注意：C++ 移位次数为负或达到类型位宽时不能据此期待“自动取模”。程序显式归一化循环位数，并保证实际 64 位移位次数在 $0$ 至 $63$ 之间；完整字掩码单独处理。

## 查询、正确性和代价

查询取 $L\mathbin{\&}65535$ ，使用大写十六进制输出，之后恢复十进制输出状态。零输出为 `0` ，没有额外前缀或补零。

初始两字均为零，表示正确。区间掩码恰好翻转指定位置，循环移位公式保持每一位的规定去向，查询提取最低十六位。因此对操作序列归纳，所有输出正确。

宽度固定为 $128$ ，每次操作使用常数次字运算，总时间 $O(N+1)$ ，额外空间 $O(1)$ .程序见 [std.cpp](std.cpp)。[循环起点与线段树](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp)保留出题人另一种方案，旋转只改起点，适合解释可扩展的环形区间维护；本题固定宽度下整数方案更直接。两份程序均通过完整正式数据。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。