# 四分枚举与有序乘积流

空间优先的并列方案。Codex（GPT-6）：将 Schroeppel–Shamir 的四分与堆生成思想应用于带权乘积阈值概率，实现并验证 [alternative-streaming.cpp](alternative-streaming.cpp)。本方案保留[主解法](solution.zh.md)的小阈值 DP、确定性预处理与共同概率因子，仅替换大阈值部分。它有明确空间优势，但不能通过当前完整时限。

## 四个小列表

先把剑分成大小尽量相等的左右两半，再把每一半分成大小尽量相等的两组，得到四组。每组独立有序生成倍率与权重列表，只保留小于最大阈值的部分乘积，记为 $A,B,C,D$ .每个列表至多有 $2^{\lceil n/4\rceil}$ 项。

左半的完整列表是所有 $A_iB_j$ ，右半是所有 $C_iD_j$ .不把它们全部存入内存，而是按需要生成下一项。

## 用堆合并乘积行

固定 $A_i$ 时，由于所有倍率为正且 $B$ 有序，$A_iB_0,A_iB_1,\ldots$ 也有序。把每行的第一项放进最小堆。每次取出最小乘积，再把同一行的下一项放进堆，便得到整个左半列表的升序流。

右半类似，但每行从最后一项开始，使用最大堆得到降序流。每个堆元素记录所在行、列、乘积及两项权重的乘积。重复倍率仍对应不同组合，不能忽略其权重。

对一个询问，先计算右侧全部行的权重总和，即 $C$ 列表权重和与 $D$ 列表权重和之积。依次取出左流中倍率 $x<K$ 的项；从右流移除所有倍率大于 $\lfloor(K-1)/x\rfloor$ 的项，并从剩余权重总和中减去其权重。左项权重乘剩余右权重，就是该左项对不达标概率的贡献。汇总后乘共同因子，再用 $1$ 减去它。

每个询问重新建立两个流，四个小列表可以复用。堆内的半边乘积在最大阈值 $M$ 处截断：先用 $a>\lfloor(M-1)/b\rfloor$ 判断，成立时保存 $M$ ，否则才计算 $ab$ .全部计算使用 `int64_t` .一个四分组达到 $M$ 的组合已被删除，因为它不可能属于任何不达标事件；两个保留的四分组相乘达到 $M$ 时，可以留作截断的堆节点，由扫描排除。

## 正确性

四个小列表恰好包含各组所有仍可能参与不达标事件的触发组合。固定一行的所有配对按列单调，每次堆弹出全部行首中最小（或最大）的元素，所以有序流恰好枚举完整半边分布，且没有重复生成或遗漏配对。

左倍率增加时，已经移除的达标右项仍然达标；尚未移除的右项按降序排列，因此内层循环结束时，剩余权重恰好对应当前左项的全部不达标右项。每个不达标组合的四个部分都小于最大阈值，因而没有被提前剪枝。左右权重相乘并汇总，乘共同概率因子后取补事件，得到要求的概率。

## 复杂度与适用条件

记 $N=2^{\lceil n/2\rceil}$ 、$H=2^{\lceil n/4\rceil}$ .四个小列表与堆占用 $O(H)$ 空间。每个询问输出至多 $O(N)$ 个流元素，每次堆操作花费 $O(\log H)$ 时间，所以大阈值部分为：

$$
O(n\log P+H+qN\log H)\text{ 时间},\qquad O(n+q+H)\text{ 空间}
$$

小阈值部分仍采用主解法。与主方案相比，指数空间的指数约减半，但不能在多个询问之间复用完整半边分布，每个询问又有堆维护开销。它适合空间不足而时间较宽松的环境；主方案适合本题的时间约束。独立小规模检查与正式压力点的限时结果见[测试说明](tests/README.md)。

计算程序复用完整的 [std.cpp](std.cpp) 中的 DP 与基础函数；编译补充程序时，`SWORDS_LIBRARY_ONLY` 仅关闭标程入口。