# 端倪发生器：出现位置二分方案

贡献：沿用出题人的前缀和分块思路；Codex（GPT-6）补齐完整块区间答案，并用出现位置二分去掉块乘值计数矩阵，给出证明与实现。二分查找是经典方法。本方案与[主解](solution.zh.md)并列，支持相同完整范围。

## 保留的统计与省去的矩阵

仍把零和子区间转为同值前缀位置对，按宽度 $B=\lceil\sqrt{N+1}\rceil$ 分块，预计算每个完整块区间的距离和 $H[s][t]$ .固定左块向右扫描，使用“已出现次数乘当前下标减去已出现下标和”累计，时间 $O(NK)$ ，其中 $K$ 为块数。

每个值 $v$ 只保留有序出现下标表 $J_v$ 及局部前缀和 $Z_v$ ，不存 $C[b][v]$ 矩阵。若完整中间区间为 $[F,G)$ ，通过两次二分求

$$x=\operatorname{lower\_bound}(J_v,F),\qquad y=\operatorname{lower\_bound}(J_v,G).$$

这里 $x,y$ 是从零开始的插入位置。则中间同值次数为 $y-x$ ，下标和为 $Z_v[y]-Z_v[x]$ .位置表按值连续存入扁平数组，每个值保留一个前缀零，避免大量小容器。

## 查询与正确性

询问前缀下标区间 $[L,R]$ 的中间完整块和两端散块划分与主解一致。中间配对查 $H$ ；左散点 $i$ 与中间配对贡献为 $z-ci$ ，右散点为 $ci-z$ ；按递增顺序扫描两端散点，用临时次数和下标和补齐所有散块配对。没有完整中间时直接扫描至多两块。每个值的中间统计在当前查询内缓存一次，结束后只清除访问过的临时项。

有序位置表中，大于等于 $F$ 且小于 $G$ 的元素恰好处于插入位置 $x$ 到 $y-1$ .因此二分得到的次数和下标和与主解矩阵完全一致。完整块、交叉、散块三类位置对仍互斥且穷尽；结合零和与同值前缀的一一对应，答案正确。上一答案精确解码下一查询的归纳同样适用。

## 复杂度与取舍

预处理 $O(N\log N+NK)$ ，每问 $O(B\log(N+1))$ 最坏时间，空间 $O(N+K^2)$ .平方根块宽下空间为 $O(N)$ ，相对于主方案的 $O(N\sqrt N)$ 矩阵有明确优势。实际二分长度是该值的出现次数；重复散点使用缓存，不重复二分。

位置前缀和、配对贡献、完整答案及异或使用六十四位，界与主解相同。本方案通过全部正式范围，适合较小内存或块乘值矩阵缓存命中较差的场合；主解具有更好的每问最坏渐进时间。五轮时间及实际内存见[测量记录](../../../docs/benchmark-R26.json)，不根据某一份输入断言其中一方在所有分布上更快。

程序：[alternative.cpp](alternative.cpp)。全部正式答案与主方案及独立莫队核验一致，小规模另用子区间枚举检查。