# 梳形构造：多尺度乘积界与混合层高 关于单棵树、线性轮数后的候选数量、固定常数倍模板的精确计数，以及为什么该构造仍不超过三次方，另见带图示的[梳形树问答](comb-candidates.zh.md)。 ## 单前缀乘积界在多个尺度上都能达到同阶 不能用一个统一阈值把候选数提前降到线性：不存在绝对常数 $C$，使所有森林都满足 $|P|>Cn\Rightarrow|A(P)|\le Cn$。 取整数 $s\ge2$，令 $n=4s^2$。放置 $2s$ 层梳子，每层主干是一整行道路，所有偶数列向下伸出 $2s-2$ 格长的齿，相邻层之间留一行空格。它们构成诱导森林。模板也是梳子，宽度为 $2s^2$，齿的位置和高度相同。只有模板主干与某层主干对齐、且起始列为偶数的平移合法，所以精确地有 $$ N=8s^4,\qquad |P|=2s^3,\qquad |A(P)|=2s^3+2s. $$ 于是 $|P|/n$ 和 $|A(P)|/n$ 同时趋于无穷，而 $|P|\,|A(P)|=\Theta(nN)$。还可以把宿主改成单一诱导树：删除每层最右侧偶数列的齿，将最右列全部设为道路，以它连接各层主干。此时 $N=8s^4+2s$，且 $|P|=|A(P)|=2s^3$，反例仍成立。 更一般地，层数取 $g=\lfloor(n+1)/(h+2)\rfloor$，齿高为 $1\le h\le n-1$，模板宽取 $\lfloor n/2\rfloor$。同样得到 $$ N=\Theta(n^2),\qquad |P|=\Theta(n(h+1)),\qquad |A(P)|=\Theta\!\left(\frac{n^2}{h+2}\right). $$ 所以单前缀乘积界在从线性到二次方的多个模板尺度上都是紧的。每个高度在这里使用不同的宿主；不能把它们的费用直接累加成同一输入上的对数下界。 ## 混合层高的梳子：按候选存活轮数消去对数 上述族也允许在同一张图中混合不同高度。设各层齿高为正整数 $h_1,\ldots,h_g$，仍以空行隔开，满足 $\sum_i h_i+2g-1\le n$。记 $$ S=\sum_i h_i,\quad H=\max_i h_i,\quad K=|\{i:h_i=H\}|,\quad N=gn+\lceil n/2\rceil S. $$ 查询先完成从左向右、宽度为 $2\le w\le n$ 的模板主干，再以任意交错顺序，把偶数列上的全部齿增长到高度 $H$。令 $$ t=\lceil w/2\rceil,\qquad a=\left\lfloor\frac{n-w}{2}\right\rfloor+1. $$ **这个限定构造族的严格界是** $$ W\le N+g\sum_{j=1}^{w-1}(n-j)+a(tS-K)\le(2n+1)N. $$ 证明如下。完成主干后的候选数为 $g(n-w+1)$。首次竖直过滤使奇数列起点全部失败；每层还有 $a$ 个偶数列起点。高度为 $h_i$ 的层中，每个这样的起点至多成功检查 $th_i$ 个齿上新格。若 $h_i