# 连续内存中的字符串函数

**出题人解法：** 前缀和定位数组，用连续内存模拟，并先检查后修改。**Codex（GPT-6）贡献：** 利用二进制字符串结构，将查询首个零和区间赋值放入线段树；补充复杂度证明、数值安全实现与测试。

## 地址与错误优先级

用长度前缀和把 $(x,y)$ 转成全局地址 $p_x+y$ .计算地址与区间终点时使用 64 位整数。先判断实际访问区间是否处于 $[0,S)$ 内，再判断复制区间是否重叠，最后判断是否跨越各自指定数组的边界。

复制与长度查询都需要找到源地址起的第一个零。若不存在零，则一定越过全局内存。复制的两个半开区间都包括结束字节；若两者起点的最大值小于终点的最小值，就发生重叠。所有检查通过后才更新。零长度写入在任何地址检查之前直接成功。

## 首选：区间赋值与首零查询

内存中的每个字节都是零或一。因此任何合法字符串都形如若干个一，后跟一个零。找到源串长度 $t$ 后，复制只需要把目标前 $t$ 个字节赋成一，再把后一个字节赋成零；无需逐字节读取源串。

线段树维护每段零的数量，以及整段赋值的懒标记。寻找位置 $p$ 之后第一个零时，跳过位于 $p$ 之前或零数量为零的结点，并优先访问左子树。每次区间赋值和首零查询都用 $O(\log(S+1))$ 时间。

## 正确性

初始叶子准确表示内存。区间赋值同步更新零数量与懒标记，下传后子段仍准确；首零查询按地址从小到大定位第一个可用零，所以得到的字符串长度正确。

每个操作先按规定的优先级检查所有需要访问的区间，拒绝时不更新。成功写入执行指定的常量赋值；成功复制写入的“一段一和一个零”与源字符串逐字节完全相同。警告分别按源和目标指定数组判断。因此每次输出和更新都符合题意，归纳可得整个操作序列正确。

## 复杂度与实现

此实现用单点赋值建立树，预处理 $O(n+S\log(S+1))$ .每次操作至多常数次查询或赋值，总时间 $O(n+(S+k)\log(S+1))$ ，空间 $O(n+S)$ .树递归深度为 $O(\log(S+1))$ ，与操作数无关。

前缀和加逐字节模拟是出题人的有效解法；它更直接，内存常数较小，在当前完整数据也能通过。见[逐字节方案](solution-alternative.zh.md)与[程序](alternative.cpp)。首选线段树是因为其操作复杂度更低，不把本题的区间赋值算法归为新发明。

## 实现与验证

[标准程序](std.cpp)、[生成器](tests/generate.py)、[测试配方](tests/plan.json)。

参考环境中标准程序最慢中位数 0.042465 秒，峰值 5.37 MiB，校准时限 0.5 秒。每例独立运行五次。

[评测环境](../../../docs/评测环境与性能.md)与[逐次时间和哈希](../../../docs/benchmark-R31.json)。数值只适用于所记录环境，迁移评测机需重新校准。