# 信号网络：循环起点与区间异或标记

出题人解法：循环起点结合线段树。Codex（GPT-6）：整理为标准 C++17 的递归区间访问，明确环绕拆段与位序。程序为 [alternative.cpp](alternative.cpp)，作为[整数方案](solution.zh.md)的补充，通过完整正式数据。

## 环形表示

物理位置始终不动，记录当前最低位对应的物理起点 $s$ .逻辑位 $i$ 对应物理位 $(s+i)\bmod B$ ，本题 $B=128$ .循环右移 $k$ 位时，只需令 $s\leftarrow(s+k)\bmod B$ .

将要取反的逻辑区间映射到物理环上，按长度展开；若跨过末端，就拆成末尾和开头两段。每段在线段树上进行区间取反。

## 线段树如何表示位

每个线段树结点只保存一个异或标记，表示其区间整体被翻转的奇偶性。区间完全被更新覆盖时翻转这个标记；部分覆盖时递归相交孩子。无需向下推送标记。

一个物理位的值等于从根到对应叶子的全部标记异或。查询时携带祖先标记的异或，递归到需要读取的叶子，将每个位放入相应的输出位。取反区间的线段树分解恰好覆盖更新位置，因此被覆盖叶子的根到叶路径恰好多经过一次翻转，其他叶子不变。

查询逻辑最低 $W=16$ 位时，也按环绕拆成至多两段。后一段的结果左移前一段的长度，再按位或合并。物理起点的映射保证两段中每个位都恢复到正确逻辑位序。相邻查询之间若没有任何修改，可以复用缓存答案。

## 复杂度与取舍

令 $R,F,Q$ 分别为旋转、取反、查询次数。建立标记数组为 $O(B)$ ；旋转为 $O(1)$ ；取反为 $O(\log B)$ ；未缓存查询访问两个边界路径及至多 $W$ 个叶子，为 $O(\log B+W)$ .总时间上界为

$$O\bigl(B+R+F\log B+Q(\log B+W)\bigr)$$

空间为 $O(B)$ ，递归深度为 $O(\log B)$ .缓存命中只需常数时间。这里 $B,W$ 固定，所以总时间也随操作数线性增长，但区间遍历的常数比两个机器字大。它的价值在于把旋转与物理存储分离，展示更一般的环形区间思路；本题首选直接字运算。

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