# 固定水平标签的交集森林

**历史研究记录（2026-10-12 更新）。** 一般三次方上界现已由[独立证明](cubic-bound.zh.md)解决。下文保留各阶段的推导、余项和反例；“尚未解决”指当时状态或该局部方法，更强的辅助命题不自动随一般上界成立。

本文用面积势能证明：所有非空水平平移交集都连通的查询，满足 $W\le2nN$。这覆盖任意根、任意访问顺序的直主干直齿梳形查询。第十五节另证明一个不限制查询的宿主子类：每对相邻行的竖边列差重数至多为常数时，扫描量仍为 $O(nN)$。本篇形成时，一般标签的总量界仍未证明，一般最坏复杂度介于 $\Omega(n^3+m)$ 与 $O(n^3\log(n+1)+m)$ 之间；后续的一般证明已结束这一缺口。

## 1. 成功事件与最早星心

令道路诱导森林为 $F$，点数为 $N$，棋盘边长为 $n$。查询根为零，按首次发现顺序增长的连通前缀记为 $P_j$。候选在时刻 $j$ 成功，要求整个平移前缀包含于道路中。

对每个道路目标 $v$，保留所有成功的非根查询点，并按以下两项分组：

- 从查询根出发的第一条子边；
- 查询点的行坐标。

每组的最早成功点为星心 $e$。其后每个成功点 $f$ 与星心组成一个标记。定义其标签和晚端候选为

$$
h=f-e=(0,d),\quad d\ne0,\qquad a=v-f.
$$

也可以只保留全局根高度记录，重新选星心，得到高度记录版。后者不直接计数全部成功事件，不能与全部成功版混用。

## 2. 交集森林与总资源

固定非零水平标签，定义

$$
G_h=F\cap(F-h)=\{z\in F:z+h\in F\}.
$$

这是诱导森林。对一个真实标记，两份成功前缀给出

$$
a+P_f\subseteq F,\qquad a+h+P_e\subseteq F.
$$

这里用查询点下标表示截至该点首次发现的前缀。由于早前缀包含于晚前缀，

$$
\boxed{a+P_e\subseteq G_h.}
$$

于是标记可关联到有向边 $a\to a+e$，并使用交集森林中连接两端的唯一树路径。整份早前缀都在交集内，而不只是该路径或两个端点。关联边本身未必是四邻接边。

若第 $r$ 行有 $k_r$ 个道路点，对所有带正负方向的水平标签求和，恰好计数同行不同道路点的有序对：

$$
\boxed{\sum_{d\ne0}|G_{(0,d)}|
=\sum_r k_r(k_r-1)\le(n-1)N.}
$$

记全部成功版在标签 $h$ 下的标记数为 $M_h$，总成功检查数为 $S$。每目标至多有四倍棋盘边长个星心，每个候选又最多失败一次，因此

$$
W\le N+S\le(4n+1)N+\sum_hM_h.
$$

所以若存在统一常数，使

$$
M_h\le C|G_h|,
$$

就能得到

$$
W\le[4n+1+C(n-1)]N.
$$

**固定标签的这个不等式仍是待证目标。** 表示式和总资源恒等式都不能自行保证标记重数受控。

## 3. 路径容量的精确局部条件

允许把每个标记分配到其关联路径上的任意顶点，每个顶点接收至多正整数 $C$ 个标记。存在这样的分配，当且仅当对交集森林的每个非空连通顶点集 $K$，完整路径位于 $K$ 内的标记数至多为 $C|K|$。

必要性直接成立。为证充分性，取任意标记子集，把其路径的并分成连通分量。每条路径完整位于其中一个分量，而每个分量都是交集森林的连通子树。逐分量应用所给条件，便得到这个标记子集的总可用顶点容量至少为标记数。把每个顶点复制 $C$ 份，Hall 定理给出分配。

这是等价归约，不是局部密度界的证明。它也比全局不等式 $M_h\le C|G_h|$ 更强；局部容量失败并不自动否定全局计数界。第九节将严格否定全部成功版的一般常数路径容量；单位标签及高度记录版不受那个反例否定。

## 4. 单位水平位移可以严格支付

**命题。** 对 $h=(0,1)$ 和 $h=(0,-1)$，全部成功版与高度记录版都可以把各标记分配到不同的源点。因此两版均满足完整路径单位容量。

只证正向。交集森林不能有竖边，否则该边及其右移一格的像在道路中构成单位方环。故每个交集分量都是水平路径。

取标记，由完整早前缀的连通性，整个早前缀必须是水平区间。写

$$
e=(0,k),\qquad f=(0,k+1).
$$

晚端后发现，且早晚端属于同一根第一子边组，故 $k\ge1$，均在右根分支。早端时前缀可写为 $[-L,k]$。

全部成功版取 $j=1$。高度记录版取右根分支中第一个全局根高度记录 $(0,j)$。由于早端本身被选中，该点必存在，并且 $1\le j\le k$。在该点发现时，前缀是 $[-L_j,j]$，且 $L_j\le L$。

令

$$
b=v-(0,j)=a+(0,k+1-j).
$$

在包含这些点的水平线上，候选的完整前缀像是

$$
[a_x+k+1-j-L_j,\ a_x+k+1],
$$

包含于晚端候选已覆盖的

$$
[a_x-L,\ a_x+k+1].
$$

所以该候选在查询点 $(0,j)$ 确实成功。它与原早端属于同目标、同根分支、同行的组。最早星心条件强迫 $k=j$。

对于整个固定正单位标签，早端及晚端因此各为一个固定查询点。同一源不可能产生两个不同标记。把每个标记分配到其源点即可；源点在自己的关联路径内。负向由水平反射得到。

这里仅消除了两个单位标签，没有建立其他水平位移的界。

## 5. 关联边组成的图可以有任意多环

不能把交集森林的无环性直接转移到关联图。[历史第三长臂反例](complexity-branches.zh.md)中的周期族，取三的倍数 $H\ge12$，在归零的（行，列）坐标下令

$$
h=(0,6),\quad A=(-2,0),\quad B=(-4,-4),\quad w_y=(y,-4).
$$

此前已经验证的内外标记分别产生

$$
A\to w_y,\qquad B\to w_y.
$$

高度记录版可取

$$
y\in\{H-2\}\cup\{H-3,H-6,\ldots,3\},
$$

所以包含 $K_{2,H/3}$。全部成功版甚至对每个 $3\le y\le H-2$ 都成立，包含 $K_{2,H-4}$。

全部成功版还需排除一个非记录早点：原构造横纵坐标下的 $(-2,y)$ 要命中 $(2,y)$，其候选平移为 $(4,0)$，但查询根像 $(4,-2)$ 缺失。原点列的早点需要平移 $(2,0)$，根旁左叶像缺失；顶部的额外早点需要平移 $(5,0)$，也缺失该左叶的像。因此早星心没有提前。外层早端仍为该行首个发现点，完整前缀与原族相同。

由于 $K_{2,k}$ 有 $2k$ 条边、$k+2$ 个活跃顶点，当参数增长时，关联图既不是森林，也不是伪森林；只使用两个端点、每点容量一的方案同样不成立。另一方面，该族满足

$$
|G_{(0,6)}|=6H.
$$

因此此反例没有否定使用全部交集顶点的常数线性容量，更没有否定原算法的三次方猜想。

固定标签的同向重边一般不可能，因为源和终点唯一确定早端、晚端及宿主目标。高度记录版也不可能同时具有一条边及其反向边：两份根路径必须是同一条宿主路径的相反方向，故两个不同早端的根深度相等，与全局高度记录深度严格增加矛盾。这些限制仍允许上述无向多环。

## 6. 面积势能与查询重叠分量

设 $Q$ 为最后一个仍有候选的完整查询前缀，不包含可能清空候选的最后一点。它是一棵可平移嵌入棋盘的树。定义

$$
J_h=Q\cap(Q-h).
$$

对嵌入网格的森林 $X$，每个分量任选势能常数，沿边定义

$$
\Phi_X(y)-\Phi_X(x)=\det(x,y).
$$

无环性保证势能存在。在交集顶点定义

$$
c_h^X(z)=\Phi_X(z+h)-\Phi_X(z)-\det(h,z).
$$

沿交集的一条边，前两项的增量差恰好等于最后一项的增量。因此这个值在 $X\cap(X-h)$ 的每个连通分量内恒定。

标记的宿主关联终点为 $w=a+e$。晚候选的完整前缀包含早晚端间的路径。对这条路径平移后的行列式求和，得到

$$
\boxed{c_h^F(w)=c_h^Q(e)-2\det(h,a).}
$$

无需整个查询交集分量都被候选嵌入。宿主可以不连通，但标记的相关两点由成功前缀连接，所以势能的分量常数相消。

固定宿主交集分量及查询势能值，源点必在同一水平行。进一步固定宿主终点和第一子边组，查询早端也在同一行。该目标、该组、该行的最早星心唯一，故这些标记可注入宿主终点。相同势能值的不同查询交集分量可以合并使用这条注入。

另有不依赖最早星心的结构：固定候选和标签，它的全部标记早端位于同一个查询交集分量。取两个早端及各自晚端。早候选活过两个早端，晚候选活过两个晚端；相应两条查询连接路径的平移像，在宿主中具有同一对端点，必须重合。因此早端间的整条路径及其标签平移都属于查询树，早端间路径在查询交集内。

## 7. 新子类：所有水平交集连通的查询

此节另定义仅按查询行分组的全部成功版：每目标同行只取一个最早成功星心，不按第一子边细分。令新标记数为 $\widetilde M_h$，查询交集的不同势能值个数为 $\kappa_h$，空交集取零。此处没有沿用前文四组标记数。

势能证明无需第一子边条件。固定一个查询势能值和宿主终点后，查询早端所在行已固定；该目标、该行的最早星心唯一。因此

$$
\boxed{\widetilde M_h\le\kappa_h|G_h|.}
$$

每目标现在至多有棋盘边长个星心，故

$$
\boxed{W\le(n+1)N+\sum_h\kappa_h|G_h|.}
$$

若每个非空查询交集 $J_h$ 都连通，则 $\kappa_h=1$，得到

$$
\boxed{W\le2nN.}
$$

更一般地，若所有非空查询交集至多有 $b$ 种势能值，则

$$
W\le[n+1+b(n-1)]N.
$$

各交集的连通分量数有统一常数上界，是一个足够条件。条件针对最终有效查询树，允许任意根和发现顺序，宿主森林也可任意分叉。

具体地，取一条完整水平主干，各列可向上、向下伸出任意长的直线齿，并要求整体仍是诱导树。每列是一个含主干行的整数区间。水平平移交集的列范围是两条主干的重叠区间；每列两个竖区间的交也含主干行。因此每个非空交集都是连通的。

这种直线梳形查询，无论从哪里出发、怎样交错访问主干和各齿，在任意道路森林上都有上述三次方上界。其连通子树仍是同类梳形或单根直齿，因此只完成一部分便失败也不影响结论。旋转坐标，使用竖直标签及按列星心，得到对应的竖直主干子类。

所有事件只计首次发现的非根点，旧点回访计入移动数。最终清空候选的一次检查已包含在每候选至多一次失败的总预算中。没有成功非根点时，结论也直接成立。

## 8. 两侧交集资源与当前缺口

查询侧也有总资源界

$$
\sum_{d\ne0}|J_{(0,d)}|\le(n-1)|Q|\le(n-1)N.
$$

可以把每个标记画成从查询早端到宿主关联终点的二分边。若标记总数受两侧全部交集顶点数之和的常数倍控制，一般对数缺口也能消除；这个总量界尚未证明。

二分图的森林性却不成立：周期族同一个宿主终点已有两个查询早端。复制宿主为两个互不相邻的道路分量，保持查询不变，即得四环。完整前缀连通，命中旧目标的成功候选只能属于原分量，所以复制保留最早星心。该反例没有否定使用两侧全部交集资源的总量界。

另一种足够的、较弱形式是

$$
M_{(0,d)}\le C N\left(1+\log\frac n{|d|}\right),
\qquad 1\le|d|\le n-1.
$$

因为

$$
\sum_{d=1}^{n-1}\log\frac nd
=n\log n-\log(n!)\le n-1,
$$

正负标签总费用仍至多为 $4C(n-1)N$。该尺度形式也尚未证明。

此前固定保存实例的完整路径分配均通过，但第九节的新无限族否定了一般常数路径容量。仍可研究允许向自身完整早前缀收费的方案，或直接控制整体标签资源。正式扫描算法及题目约束未因这些归约改变。

两侧资源的渐近目标实际等价：最终有效查询存在完整合法平移，所以

$$
a_0+Q\subseteq F\quad\Longrightarrow\quad
a_0+J_h\subseteq G_h,\qquad |J_h|+|G_h|\le2|G_h|.
$$

两侧资源可能有助于构造分配，但没有放宽整体标签计数目标。

## 9. 全部成功版的完整路径容量没有统一常数

本节改用横纵坐标。取整数
$$
k\ge2,\qquad H=2k,\qquad d=2k+2,\qquad h=(d,0).
$$

查询根为原点，查询为竖干加正偶数高度上的长齿：
$$
Q=\{(0,y):0\le y\le H\}
\cup\{(x,2i):1\le i\le k,\ 0\le x\le d+k\}.
$$

实际先由下到上逐齿访问：沿竖干上行两格，向右走 $k$ 格再返回。到顶后由上到下逐齿走满全长、返回竖干，再下行两格。最终回到根。道路为
$$
\begin{aligned}
F={}&\{(0,y):-H\le y\le H\}
\cup\{(d,y):-H\le y\le0\}\\
&\cup\{(x,-2i):1\le i\le k,\ 0\le x\le k\}\\
&\cup\{(x,-2i):1\le i\le k,\ d\le x\le d+k\}\\
&\cup\{(x,2i):0\le i<k,\ 0\le x\le d+k\}.
\end{aligned}
$$

两竖干仅由高度零的长齿连接。负偶数行的左右短齿之间有空隙，正高度没有右竖干；相邻齿之间留一行。因此所列边构成诱导树，没有额外邻接成环。查询也为诱导树。计入全部回走，有
$$
N=5k^2+8k+1,\quad |Q|=3k^2+4k+1,\quad
n=4k+1,\quad m=8k^2+8k.
$$

把最终查询下移两格即可嵌入道路，所以全程有合法候选。定义
$$
\begin{aligned}
1\le i\le k,\quad&0\le j\le k,\\
e_{ij}=(j,2i),\quad& f_{ij}=(d+j,2i),\\
a_i=(0,-2i),\quad&c_i=(d,-2i),\\
w_j=(j,0),\quad&v_j=(d+j,0).
\end{aligned}
$$

早端发现时，早候选把当时的竖干放到右竖干，把更低短齿放到负偶数行右短齿，把当前齿放到高度零。晚端发现时，晚候选把完整竖干放到左竖干，把所有短齿放到相应短齿或长齿；已经延长的更高齿全部落到正偶数长齿，当前齿落到高度零。因此两份**整个历史前缀**都合法。

同一查询行中，更早点只能位于当前早端左侧。若它要命中同一目标，其候选根横坐标严格大于右竖干，纵坐标为负偶数。查询第一步向上，落在没有道路的负奇数行，因此已失败。所以指定早端确是真正最早星心。查询根只有一条子边，逐行版和旧四组版都产生这批标记。

每个标记的关联路径从左竖干的源点向上到高度零，再向右到关联终点。全部路径的并为
$$
K=\{(0,y):-2k\le y\le0\}\cup\{(x,0):1\le x\le k\},
\qquad |K|=3k+1.
$$
于是
$$
C\ge\frac{k(k+1)}{3k+1}\longrightarrow\infty.
$$

这严格否定任何统一常数的自身完整路径容量。它没有否定整体标签界：逐行计数及候选竖干位置限制给出
$$
\widetilde M_h=M_h=k(k+1),\qquad |G_h|=2k^2+3k.
$$

任意标记的晚候选竖干只能在左竖干上。早前缀要求下移至少当前齿号，晚前缀要求至多当前齿号，因此每对查询点恰由指定候选产生。

本族甚至允许向各自完整早前缀作单位分配：
$$
z_{ij}=(j,2-2i)=a_i+(j,2)\in a_i+P_{e_{ij}}\subseteq G_h.
$$

发现当前早端时，第一齿已访问到相应位置；不同指标给出不同道路点。这些资源包括关联路径之外的旧齿。完整早前缀容量的一般命题仍未证明。

本族不提供相同数量的全局高度记录标记，也不否定原算法：查询是竖直梳形，已被第七节旋转后的定理覆盖。一般构造及固定输入验证见[研究证书](../examples/local-path-capacity.zh.md)。

## 10. 取横竖两向较小势能预算仍会损失一阶

第七节的不等式正确，但其势能类型加权预算本身没有统一三次方上界。恢复（行，列）坐标，取
$$
k\ge2,\qquad b=2k+4.
$$

构造两把正交梳子：
$$
\begin{aligned}
A={}&\{(r,0):0\le r\le2k\}
\cup\{(2i,c):0\le i\le k,\ 0\le c\le2k\},\\
B={}&\{(b,c):b\le c\le4k+4\}
\cup\{(r,b+2i):0\le i\le k,\ b\le r\le4k+4\}.
\end{aligned}
$$

以先竖后横的折线连接第一把梳子的底端与第二把梳子的左端：
$$
(2k,0)\longrightarrow(b,0)\longrightarrow(b,b).
$$

两把梳子间隔四格，连接线只碰到各自端点，整体是诱导树。取查询和道路都是这棵树，根为原点，按任一完整深度优先遍历行走。则
$$
n=4k+5,\qquad N=4k^2+10k+9,\qquad m=2(N-1).
$$

每个正水平位移在第一把梳子的各水平齿上产生不同势能值；正竖直位移在第二把梳子的各竖齿上同理。具体地，
$$
1\le d\le k:\qquad
\kappa_{(0,d)}\ge k+1,\quad |G_{(0,d)}|\ge(k+1)(2k-d+1).
$$

水平齿行坐标为两倍齿号，沿齿直接计算的势能值为四倍齿号乘位移，因此确实互异。竖向交换坐标后也互异；到达第二把梳子的公共路径只增加势能常数。

令横竖预算分别为
$$
B_H=\sum_{d\ne0}\kappa_{(0,d)}|G_{(0,d)}|,
\qquad B_V=\sum_{d\ne0}\kappa_{(d,0)}|G_{(d,0)}|.
$$

正负标签成对，故
$$
B_H,\ B_V\ge
2(k+1)^2\sum_{d=1}^k(2k-d+1)
=k(3k+1)(k+1)^2=\Omega(k^4),
\qquad nN=\Theta(k^3).
$$

选择两个方向中较小的预算也无法消去这一阶损失。这只否定粗预算的总量界，不否定实际扫描数的三次方上界。完整计数见[正交双梳证书](../examples/orthogonal-combs.zh.md)。

## 11. 跨查询分量的真实时间限制

以下均使用第七节的逐行全部成功版。记查询点发现下标为 $t(q)$。对任一真实标记，
$$
R_{e,f}=P_{t(e)}\cap(P_{t(f)}-h)
$$
连通并包含早端。证明只需平移：
$$
(a+h)+R_{e,f}
=((a+h)+P_{t(e)})\cap(a+P_{t(f)}).
$$

右侧两棵合法宿主子树都包含标记目标，森林中的唯一道路保证其交连通。因此，凡是早下标不晚于本标记早端、晚下标不晚于本标记晚端的查询平移配对，均属于同一个最终查询交集分量。

特别地，不同交集分量的任意两笔同标签标记满足严格反序：
$$
t(e_1)<t(e_2)\quad\Longrightarrow\quad
t(e_1)<t(e_2)<t(f_2)<t(f_1).
$$

这是跨目标、跨候选的限制，不依赖高度记录。同分量内部不受此反序限制，不能据此把所有标记视为一条嵌套链。

若查询已首次到达有符号位移点，根也属于上述前缀交集。因此，当位移在查询中、晚端下标不小于其首次发现下标时，早端属于查询交集的根分量。所有根分量标记可以合计注入宿主终点。非根分量标记必须在首次到达该位移之前完成；相反方向的位移不能替代这个截止。

## 12. 共同切口把未付部分缩到两份固定不交子树

固定一个有标记的标签。取发现最晚的早端，定义
$$
t_*=\max_{\text{markers}}t(e),\qquad P=P_{t_*},
\qquad I=P\cap(P-h).
$$

实现最晚早端的那笔标记，其两个候选都匹配整个共同前缀。因此共同前缀及其位移副本的并可以嵌入道路，是诱导森林；两份副本的交连通或为空，旧交集也连通或为空。

若晚端已在共同前缀中，早端必在旧交集中。对于跨切口标记，若晚候选的共同前缀像与早候选的早前缀像相交，则存在
$$
x\in P_{t(e)},\qquad x+h\in P.
$$

两份完整合法宿主前缀同时包含交点及标记目标。唯一道路性迫使查询中连接该交点与早端的整条路径及其位移像都存在。因此早端连接到旧交集所在的最终查询分量。已完成标记及上述相交标记**合计**只需一次宿主交集点数。

相交条件与候选位置无关，恰为早前缀遇到旧交集。定义
$$
\tau=
\begin{cases}
\min_{q\in I}t(q),& I\ne\varnothing,\\
t_*+1,&I=\varnothing,
\end{cases}
\qquad R=P_{\tau-1},
$$
其中下标负一的前缀为空。所有未付标记统一满足
$$
\boxed{
e\in R\subseteq P,\quad f=e+h\in R+h,\quad
P\cap(R+h)=\varnothing,\quad t(e)\le t_*<t(f).
}
$$

所有晚候选仍匹配同一个共同前缀；早候选可以在切口前已经失败。记这部分标记数为剩余量，则
$$
\boxed{\widetilde M_h\le |G_h|+\widetilde M_h^{\rm separated}.}
$$

若有符号位移已在共同前缀内，旧交集含根、剩余前缀为空，得到
$$
h\in P\quad\Longrightarrow\quad \widetilde M_h\le |G_h|.
$$

一般情况下，仅由静态模板乘积界还只能推出
$$
|R|\le |P|-|I|,\qquad
\widetilde M_h^{\rm separated}
\le |A(P)|\,|R|
\le (2n-1)N\frac{|R|}{|P|}.
$$

尚未证明这些剩余量可跨标签统一支付。第九节表明可用道路资源必须允许关联路径外的旧分支；第十节表明直接为每个势能类型重复支付全部交集资源也过于粗糙。一般对数缺口仍在。

## 13. 完整早前缀容量及早端不重复的子族

以下仍用逐行全部成功标记。每笔标记允许使用的资源现在是整份早前缀
$$
S_{a,e}=a+P_{t(e)}\subseteq G_h.
$$

它是连通子树。与第三节相同的 Hall 论证说明，容量为正整数常数，当且仅当每个非空连通子树内完整包含的资源数不超过该子树的容量总和：
$$
\#\{(a,e,f):S_{a,e}\subseteq U\}\le C|U|
\qquad\text{for every connected }U\subseteq G_h.
$$
这比只界整个标签的标记数更强，一般结论仍未证明。

一个有用的严格特例是：**查询早端互不重复的任意标记子族，都有单位分配。** 任取其中若干笔，最晚早端的完整前缀已经包含所有这些不同的非根早端和查询根。因此这一份资源的点数，就严格多于所取标记数。每个子族都满足 Hall 条件，得到单位匹配。

同源标记的早端必不重复；同一查询势能类型则可直接注入宿主关联终点。困难必须同时涉及多个源、多个类型及重复早端。不能把“同一宿主交集分量中多类型与重复早端互斥”当作定理：已有合法混合反例，详见[构造证书](../examples/mixed-types.zh.md)。

## 14. 每行竖边数控制完整早前缀容量

使用（行，列）坐标。对非空连通子树，定义其相邻行间最多有多少条竖边：
$$
b(U)=\max_r\#\{c:(r,c),(r+1,c)\in U\}.
$$

**定理。** 资源完整落在该子树内的真实标记，具有容量至多为下式的分配：
$$
1+b(U).
$$

令首次发现根水平行以外点的时刻为首竖边时刻。在此之前，完整查询前缀都在根行。所有这类早端同属查询行零，逐行最早星心保证宿主关联终点不重复，所以这部分有单位分配。

首竖边及其两个端点是固定的：
$$
q\longrightarrow q+\delta,\qquad
\delta\in\{(1,0),(-1,0)\},\qquad q_r=0.
$$
从该时刻开始，每份早前缀都包含此边。固定一个查询早端，资源在同一个宿主交集分量内，面积式
$$
c_h^F(a+e)=c_h^Q(e)-2\det(h,a)
$$
使所有相应源的行坐标唯一确定。首竖边的宿主像
$$
a+q\longrightarrow a+q+\delta
$$
于是必须从同一宿主行、朝同一方向出发，选择数至多为该子树的竖边参数。选定像边又唯一确定候选源及标记。因此，同一个早端在这一类中至多重复该参数次。

按同一早端的出现次数，将后半类分成若干组，每组早端互不重复。第十三节给每组单位容量，与前半类的单位分配叠加，便得定理。若查询第一步就是竖直，前半类为空，容量可改为
$$
b(U).
$$

证明只使用原实例的完整前缀和真实星心，没有删除子树外的晚前缀历史。空的一类不用支付容量。水平直路径只有前半类，竖直直路径只有后半类，两者都具有单位容量。每对邻行至多穿越一次的纵向单调路径具有容量至多二；任意折返路径不满足这个参数限制。

各资源完整落在唯一的宿主交集分量内，故
$$
\widetilde M_h\le
\sum_{K\in\operatorname{comp}(G_h)}[1+b(K)]|K|.
$$
一般森林中该竖边参数可以增长，所以这还没有解决一般界。

## 15. 新宿主子类：竖边列差的重数有常数上界

对每对相邻道路行，收集连接它们的竖边列坐标：
$$
C_r=\{c:(r,c),(r+1,c)\in F\}.
$$
假设对所有行和所有非零有符号列差，都有
$$
|C_r\cap(C_r-d)|\le b\qquad(d\ne0).
$$
这里的常数约束针对道路，不限制查询根、发现顺序或分叉。

固定水平标签时，宿主交集中相邻行间的竖边列恰为上述列集合的平移交集：
$$
h=(0,d),\qquad
\{c:(r,c),(r+1,c)\in G_h\}=C_r\cap(C_r-d).
$$
因此每个交集分量的竖边参数都至多为给定常数。应用第十四节并对全部有符号标签求和，得到
$$
\boxed{
\widetilde M_h\le(b+1)|G_h|,\qquad
W\le[(b+2)n-b]N.
}
$$
这证明该宿主子类上的任意查询均为三次方时间。若查询第一步竖直，还可得到
$$
W\le[n+1+b(n-1)]N.
$$
最后全灭的失败检查仍由每候选至多一次失败支付；回访计入实际移动数。

### 一个稠密且分叉超过线性数量的树族

取任意奇素数，并定义
$$
p\ge3,\quad
a_i=2pi+(i^2\bmod p)\quad(0\le i<p),\quad
H=2p^2,\quad w=p-1.
$$
道路由行零的水平底边、这些列上的完整竖干，以及正偶数行上的右向短齿组成：
$$
\begin{aligned}
F={}&\{(0,c):0\le c\le2p^2-p\}\\
&\cup\{(r,a_i):0\le i<p,\ 0\le r\le H\}\\
&\cup\{(2j,a_i+x):0\le i<p,\ 1\le j\le p^2,\ 1\le x\le w\}.
\end{aligned}
$$
相邻竖干至少相隔素数加一格，齿长为素数减一，故各齿与下一竖干之间仍有空列；齿之间隔一行。底边只在各竖干底端连接它们，整体是一棵诱导树。

竖干列的非零差值唯一。若两对列差相等，剩余项之差的绝对值小于两倍素数，先得到两对下标差相同。再模素数计算，并利用差非零、二可逆，得到两对下标分别相同：
$$
a_i-a_j=a_u-a_v,\quad i\ne j
\ \Longrightarrow\
i-j=u-v,\quad
(i-j)(i+j)\equiv(u-v)(u+v)\pmod p
\ \Longrightarrow\ (i,j)=(u,v).
$$

每对相邻行的竖边列集合都恰好是这些竖干列，所以重数参数为一。精确规模为
$$
n=2p^2+1,\qquad
N=p^4+p^3+2p^2-p+1,\qquad
B=p^3-1.
$$
道路数按底边、竖干新增点、齿新增点分别计数。分叉数按各竖干的非顶层正偶数行，以及底边上除首竖干以外的连接点计数。

因此
$$
N=\Theta(n^2),\qquad B=\Theta(n^{3/2}),\qquad
W\le(3n-1)N.
$$
这是稠密的单个道路分量，已经超出“每分量只有线性多个分叉”的旧条件。上述上界对所有查询成立，不依赖示例的特定走法。

## 16. 一条连通竖直查询段上的早端可作单位分配

固定查询树中的一条连通竖直段，只取早端位于其上的标记。为每笔标记使用较小资源
$$
T_{a,e}=a+(P_{t(e)}\cap V)\subseteq S_{a,e}.
$$
查询前缀和该竖段都是树中的连通子树，交集包含早端，因而是非空竖直段。

仅保留宿主交集的竖边，将它拆成互不相交的竖直段。每份较小资源完整落在其中一段。固定宿主竖段及查询早端，面积式固定源行，竖段所在列减去查询竖段所在列又固定源列。因此同一早端在该宿主竖段内最多出现一次。

任取这条宿主竖段内的若干笔，发现最晚的早端对应的查询交集包含所有选中的不同早端。其资源大小至少等于选中标记数，给出 Hall 条件。各宿主竖段点集不交，合并后仍是单位分配。查询根不必位于所选竖段内，旧分支也全部保留在成功条件中。

同一查询水平行上的早端可直接注入宿主关联终点。所以，若早端集合可被 $u$ 条查询水平行和 $v$ 条连通查询竖段覆盖，则完整早前缀容量至多为覆盖件数：
$$
C\le u+v.
$$
重叠覆盖时先把每笔标记任意指定给一件。这个参数在一般查询上可以增长，尚不能作为统一常数使用。

## 17. 候选源共线的子族有单位容量

固定水平标签。若一个真实标记子族的候选源共线，其完整早前缀资源可作单位分配。

先限制在一个宿主交集分量内。若源直线水平，面积关系使所有查询势能类型相同；第七节逐行标记的终点注入直接给出分配。若直线不水平，固定早端后，面积关系唯一确定源行，而这条直线与该行至多交于一点。因此早端不重复，第十三节给出单位 Hall。

不同宿主交集分量的资源互不相交，可以合并这些分配。这个结论不要求源直线与网格轴平行，也不排除根行早端。但若把任意源集合拆成多条直线，各组可能复用资源；目前没有可将各组费用直接相加的总量界。

## 18. 资源相交图连通也不能保证类型分离

第十三节提到的混合现象，即使要求实际资源通过共享顶点连接，也仍然存在。一个固定合法实例满足
$$
n=30,\qquad N=118,\qquad |Q|=60,\qquad m=126,\qquad W=421.
$$
采用（行，列）坐标，标签及该标签的统计为
$$
h=(0,20),\qquad \widetilde M_h=14,\qquad
\left|\bigcup S_{a,e}\right|=31.
$$
它有两个查询势能类型，三个早端各重复两次。其中一笔资源与另外每笔资源共享顶点，所以资源相交图有一棵以它为中心的生成星。这否定了在实际资源相交分量内，将全部标记分成“单类型”或“早端不重复”两类的做法。

这十四笔仍可分配到十四个不同的自身资源点。因此该例没有否定完整早前缀 Hall，也没有否定算法三次方上界。[构造证明](../examples/connected-resources.zh.md)列出完整道路坐标、实际走法、真实最早星心和显式单位分配；

## 19. 同早端重复的交换关系与树轴长度

固定宿主交集分量，取早晚端相同、源不同的两笔真实标记：
$$
K\in\operatorname{comp}(G_h),\qquad
(a,e,f),\ (b,e,f),\qquad a\ne b.
$$
相关道路位于同一宿主树：完整晚前缀连接各自的早晚端，资源又接入同一个交集分量。

### 从方向词得到交换关系

用东西和南北两对互逆字母记录道路路径。树上简单路径没有立即回头，其方向词已经约简；以一个宿主点为根，这将道路树等距嵌入自由群的 Cayley 树。连通道路子树之间保持边方向的平移，由同一个左乘映射表示。

令交集分量的水平平移对应左乘映射，两个完整晚前缀之间的平移对应另一个：
$$
g:K\longrightarrow K+h,\qquad
T:a+P_f\longrightarrow b+P_f.
$$
在早端像处，完整前缀保证四角都存在：
$$
w=a+e,\qquad
gT(w)=b+f=Tg(w).
$$
左乘映射若在一个顶点相同，其群元素就相同。因此
$$
\boxed{Tg=gT.}
$$
查询根包含于完整前缀，所以同时有
$$
T(a)=b.
$$
两映射的网格位移分别为非零的水平标签和源差，故均非恒等。证明没有使用私人端点，也不受根行例外影响。

### 同一早端的源必须占用不同轴投影

非平凡自由群左乘有唯一的双向平移轴，记为 $L$。可将它写成一个循环约简非空词的共轭；先将这个词向两端反复拼接，再按共轭前缀左乘平移，得到原映射的轴。离轴顶点的位移长度等于轴上平移长度加两倍离轴距离，因此该轴唯一。

由交换式，源之间的映射保持这条轴。它不能在轴上反射，否则会反转非零平移；也不能逐点固定轴，否则自由左乘就是恒等。因此它沿轴作非零整数平移。同一个早端的不同源到轴距离相同，轴投影两两不同。

取至少两笔这样的标记，并假设其完整资源都包含于一个连通子树。记共同离轴距离为下式中的距离参数，最远轴投影间距为跨度：
$$
k\ge2,\qquad S_{a,e}\subseteq U\subseteq K,\qquad
r_e=\operatorname{dist}(a,L),\qquad
D=\max_{a,b}\operatorname{dist}(\pi_L(a),\pi_L(b)).
$$
连通子树包含任意两源间的唯一树路。轴不必整体位于道路中，但投影之间的轴段及每个源到其投影的连接段都被这些道路路径强制包含。不同投影的离轴连接段互不相交，故
$$
\boxed{|U|\ge k r_e+D+1\ge k(r_e+1).}
$$
至少两笔的条件不能省略：只有一个源时，其到轴的连接段未必位于资源中。

这只约束一个固定早端的重复。不同早端可以复用同一源到轴的连接段，尚不能对它们直接相加。一般完整前缀容量和固定标签的线性总量界仍未证明。

## 20. 树轴重复次数有界时，剩余标记有常数容量

本节按源投影分组得到的常数，在第二十七节改用资源左端点后进一步减小；这里保留原证明。

第十二节已将一个标签的标记拆成一次交集费用和共同切口后的剩余量。每笔剩余标记的完整早资源与其标签平移不交：
$$
S\cap(S+h)=\varnothing.
$$
事实上其早端在更早前缀内，完整早前缀也包含于该前缀，而该前缀的标签平移与共同晚前缀不交。这保留全部候选历史。

### 最短轴周期与分段

固定含有剩余标记的宿主交集分量，沿第十九节的轴取整数坐标，使映射向正方向平移。所有与该映射交换的自由群左乘，在轴上的有符号位移构成非零整数子群。位移为零者固定轴顶点，只能是恒等。因此存在一个最小正轴位移，并有
$$
\ell_g=q_K\ell_0,\qquad q_K\in\mathbb Z_{\ge1}.
$$
这里的整数是平移词的幂次数，与网格水平距离不同。最小位移的左乘取相应次幂后与原映射在轴上一致，因而就是原映射。对网格位移取和还得到
$$
q_K\mid |d|,\qquad 1\le q_K\le |d|
\qquad\text{when }h=(0,d).
$$
所以一般实例并不自动具有常数幂次数。

将候选源的轴投影按半开区间分组：
$$
[j\ell_0,(j+1)\ell_0),\qquad j\in\mathbb Z.
$$
同一个早端的不同源，其轴投影之差是非零的最短轴位移整数倍。因此每组早端互不重复，第十三节给每组完整资源单位分配。

### 一个道路点至多被常数多个组使用

连通资源若不接触轴，其投影是单点。若接触轴，投影就是它与轴的交。由资源与其平移不交，两种情况都有
$$
\operatorname{diam}\pi_L(S)\le\ell_g-1=q_K\ell_0-1.
$$
源本身属于资源。于是一个道路点若属于某笔资源，其投影与该笔源投影的距离满足
$$
z\in S_{a,e}\quad\Longrightarrow\quad
|\pi_L(z)-\pi_L(a)|\le q_K\ell_0-1.
$$
允许的源投影区间至多穿过以下数量的分组区间：
$$
2q_K+1.
$$
每组内已作单位分配，跨组叠加后，这也是该道路点负载的上界。轴不必全部位于道路中；这里只有资源中的点被收费。

因此剩余标记在这个分量内有该容量。结合第十四节原有的竖边容量，还可取两者较小值：
$$
\boxed{
\widetilde M_h
\le |G_h|+
\sum_{K\in\operatorname{comp}(G_h)}
\min\{1+b(K),\,2q_K+1\}|K|.
}
$$
求和只需包含有剩余标记的分量；其余分量的求和项取零。一次交集费用仍统一支付已完成及触及共同前缀的标记。

特别地，若所有相关标签、分量的幂次数都有统一常数上界，则
$$
q_K\le q_0
\quad\Longrightarrow\quad
\widetilde M_h\le(2q_0+2)|G_h|,\qquad
W\le[(2q_0+3)n-(2q_0+1)]N.
$$
若相关平移词在自由群中均不是更短词的非平凡幂，得到
$$
q_0=1\quad\Longrightarrow\quad W\le(5n-3)N.
$$
这是一个严格的条件上界。一般情况下，幂次数和竖边参数都可能增长，二者较小值的加权总和仍缺控制。特别不能将所有水平位移的幂次数默认成一。

## 21. 任意局部路径内的完整早资源具有容量四

**定理。** 固定标签及宿主交集分量。若只保留完整早资源位于某条非空简单路径内的真实标记，则
$$
U\subseteq K\in\operatorname{comp}(G_h),\qquad
S_{a,e}\subseteq U
\quad\Longrightarrow\quad C_U\le4.
$$
路径可以反复折返，查询根可以位于前缀内部。不要求资源与标签平移不交，也不限制轴幂次数。条件针对完整早前缀；因此第九节只给自身根路径容量的反例不适用。

沿第十九、二十节的公共轴取整数坐标，记最短正轴周期为
$$
p=\ell_0.
$$
同早端的不同源之间的映射保持该轴，平移量是最短周期的非零整数倍。

### 轴外两条尾段各付一个单位容量

若整条路径的轴投影只有一个点，同早端的两个不同源不可能同时位于其中，故全部早端互异，第十三节直接给单位容量。

否则，路径与轴的交是非退化区间，轴外部分至多有两条尾段，分别附着在区间两端。触及同一尾段的资源，其早端不能重复。否则两份资源由非零轴平移关联，而它们的非空轴外投影集合满足
$$
A,\ A+\Delta\subseteq\{\alpha,\beta\},\qquad
\Delta\ne0,
$$
并共享所选尾段的附着点。单点集合共享一点便要求平移量为零；二点集合也不能经非零平移仍留在同一二点集，矛盾。

将轴外资源按触及的尾段分成两组，触及两尾的任选一组。每组早端互异，分别作完整资源单位分配，合计容量二。此处分配允许使用资源的轴上部分。

### 轴内短资源付一个单位容量

剩余资源都在轴上。首次发现下标满足
$$
j=t(e)=|P_{t(e)}|-1\ge1.
$$
该资源恰有这么多条轴边。先取短资源族 $\mathcal S_{<p}$，在一个任意大小的轴区间内计数：
$$
j<p,\qquad |V|=\nu.
$$
固定早端后，各副本轴向一致，源在资源内的相对位置固定。要把资源放进该区间，允许的源位置共有顶点数
$$
\nu-j\qquad(j<\nu).
$$
同早端源位置相隔最短周期的非零整数倍，所以出现次数至多为该数除以周期后向上取整。每个首次发现下标至多对应一个早端，故
$$
\#\{S\in\mathcal S_{<p}:S\subseteq V\}
\le\sum_{j=1}^{\min(p-1,\nu-1)}
\left\lceil\frac{\nu-j}{p}\right\rceil
=\nu-\left\lceil\frac{\nu}{p}\right\rceil
\le\nu-1.
$$
周期为一时该类为空。任意短资源子族的并集是若干不交轴区间，对每段使用上述界即可验证 Hall，得到单位容量。

### 轴内长资源的源同行，再付一个单位容量

对于剩余的长资源，取其中早端下标最小的一笔及其前缀。所有后续长资源都包含这份前缀的完整副本，并都在同一轴上：
$$
j\ge p,\qquad a_*+P_*\subseteq L,\qquad a+P_*\subseteq L.
$$
副本之间的左乘使原轴与其像共享至少一整周期的连续边。两条轴的双向方向词都有该周期；沿重合段选择同一个方向，一整周期的字母相同便唯一决定两端的全部延拓。因此
$$
T(L)=L.
$$
反向对齐也包含在这个论证内。保持轴的左乘不能反射：反射会固定顶点或翻转一条边，而自由群左乘均不允许。因此它沿轴平移，进而与标签映射交换。由最短轴周期的网格位移水平，所有这些源同行，第十七节给单位容量。

四组分配叠加，得到容量四；若资源全在轴内，只需容量二。证明保留根行早端，未使用私人端点假设。

若某标签的全部交集分量都是路径，可得
$$
\widetilde M_h\le4|G_h|.
$$
若所有标签均满足这一条件，则
$$
W\le(5n-3)N.
$$
后一宿主条件已属于旧的线性分叉范围：每行至多有四个分叉点，因为只有四种邻向三元组，同行两个点若具有同一三元组，其位移交集就会出现分叉。因此这里的新结论是任意局部路径的容量界，不能把全标签推论宣称为新的超线性分叉宿主子类。

一般分叉资源不能直接拆开套用本节；拆开后可能不再包含完整早前缀。

## 22. 轴分组的资源并大小不能直接相加

第二十节逐组分配的总资源可能被反复计算。取正偶数参数，使用（横，纵）坐标：
$$
s\ge4,\qquad h=(2s,0).
$$
道路是零高度上从零到五倍参数的完整横轴，并在从参数到五倍参数之间的偶数横坐标处各加一格上叶。查询实际走法及规模为
$$
E^sNS\,E^{2s}N,\qquad
N=7s+2,\qquad m=3s+3.
$$
叶子隔格，不形成诱导环。

新行首点与第二片叶子构成真实早晚对。偶数源从零到两倍参数都有完整早晚前缀匹配，其资源是一段横轴加一片叶子：
$$
e=(s,1),\quad f=(3s,1),\quad
a=(j,0),\quad j\in\{0,2,\ldots,2s\}.
$$
这一子族已有参数加一笔；完整逐行统计还必须包含根行标记，得到
$$
\widetilde M_h=\frac{5s}{2}+1,\qquad |G_h|=4s+2.
$$
这里轴最短周期为一，源各自属于不同分组。记第 $j$ 组的资源并为 $\mathcal R_j$，则一个道路点参与的组数，以及各组资源并大小之和，分别为
$$
\max_z\#\{j:z\in\mathcal R_j\}=\frac s2+1,\qquad
\sum_j|\mathcal R_j|=s^2+4s.
$$
所以逐点参与组数没有常数上界，各组资源并大小之和也不是实际资源总量的常数倍。

但所有源同行，全部真实标记可直接注入不同的关联终点。该族仍具有单位容量；精确扫描量为
$$
W=\frac{15s^2+21s+6}{2}.
$$
它只否定粗分组费用，不否定一般 Hall 或算法上界。三个固定参数的完整前缀、最早星心、原标程与独立答案核验见[构造证书](../examples/overlapping-bands.zh.md)。

## 23. 高幂分量的数量预算与一般问题的剩余项

### 交集分量是同一道路树的完整平移交

固定含真实标记的宿主交集分量。它及其标签平移都在同一道路树内；将这棵树嵌入方向词 Cayley 树，记为下式中的道路树。统一标签左乘满足
$$
K=C\cap g^{-1}C.
$$
右侧是两个凸子树的非空交，因而连通。它包含原分量；其中每点的左乘像又位于道路中，网格位移恰为该标签，所以全部属于同一个宿主交集分量，得到等式。

令该左乘的轴为轴线，道路树与轴的交为有限区间，则
$$
A=C\cap L,\qquad
\pi_L(K)=K\cap L=A\cap g^{-1}A.
$$
证明如下：对交集中的一点，它和左乘像间的唯一道路包含两端到轴的连接段以及中间轴段；两条连接段又互为左乘像，所以原连接段也完整位于交集内。于是每个交集点的轴投影仍在交集中，上式成立。

这也说明：指定道路树、一条具有水平网格周期的轴及一个有符号幂次，至多确定一个这样的交集分量。若轴交只有一个顶点，所有源的投影相同，早端不能重复，整个分量已有单位容量。

### 不同长轴的重复次数具有线性预算

这里使用一个已有结果：有边的确定性边标号有根树中，沿祖先—后代路径的极大重复段，其幂次数之和小于边数的三倍。重复段至少包含两个最短周期；孤立点没有重复段，直接贡献零。[Sugahara 等，Computing Runs on a Trie，推论 6](https://drops.dagstuhl.de/storage/00lipics/lipics-vol128-cpm2019/LIPIcs.CPM.2019.23/LIPIcs.CPM.2019.23.pdf)

给每棵道路树任选根，朝父亲的方向字母作为边标号；同一父亲的不同孩子具有不同标号，满足该结果的确定性条件。道路森林边数为
$$
N-c,
$$
其中分量数包含孤立点。

只考虑具有非零水平网格周期、且在道路内至少含四个最短周期的轴：
$$
p_L\ge1,\qquad
A_L=C\cap L,\qquad
\rho_L=\frac{|E(A_L)|}{p_L}\ge4.
$$
轴按道路分量区分。有限轴段在其最浅点分成至多两条祖先—后代路径；选较长者，长度至少为原段一半，故至少含两个周期。它的最短周期仍等于轴周期：若两个连续周期有更小周期，原周期词在模周期长度的位置上也具有更小循环周期，与最短性矛盾。

将这条祖先—后代段扩成同周期的极大重复段。确定性标号使延拓唯一；一个最短周期及其起点又决定整条双向标号轴。因此不同轴不能对应同一个极大重复段。应用上述幂次总和界，得到
$$
\boxed{\sum_L\rho_L\le6(N-c).}
$$
因子二来自选择至少占原轴段一半的祖先—后代段。这里归并的是同一轴，不能为它的每个标签重新支付一次轴预算。

### 高幂分量的数目和幂次总和

轴的最短周期有非零水平网格位移。若轴段含若干完整周期，两端的横坐标差就是该数乘周期位移，所以
$$
\lfloor\rho_L\rfloor\le n-1.
$$
每个正负有符号幂次分别至多对应一个分量。因此，令下式集合只包含含真实标记、幂次数至少四的标签分量，有
$$
\mathcal H=\{(h,K):q_K\ge4\},
$$
以及
$$
\boxed{
|\mathcal H|\le12(N-c),\qquad
\sum_{(h,K)\in\mathcal H}q_K
\le12(n-1)(N-c).
}
$$
常数十二已经包含正、负水平标签。没有在这里估计由分量大小加权的幂次和。

### 一般问题严格缩到哪些标记

沿用第十二节每个标签的共同切口。先支付已完成及触及共同前缀的标记，合计至多一次交集大小。对剩余标记，以下分量也能支付：

- 幂次数至多三：第二十节给容量至多七。
- 分量本身为路径：第二十一节给容量四。
- 轴交只有一个顶点：早端互异，给单位容量。

在有剩余标记的标签分量中，未付集合必须同时满足
$$
\mathcal C=\{(h,K):
q_K\ge4,\quad
K\text{ has a fork},\quad
|E(K\cap L)|\ge1\}.
$$
其数量及幂次总和服从上面的预算。记这些分量内共同切口后的剩余标记数为
$$
\widetilde M^{\rm separated}_{h,K}.
$$
星心、每候选至多一次失败、共同切口已付项以及非临界分量的容量合并为
$$
\boxed{
W\le(9n-7)N+
\sum_{(h,K)\in\mathcal C}
\widetilde M^{\rm separated}_{h,K}.
}
$$
系数来自逐行星心与失败费用，加八倍的全标签交集预算。

**最后这个剩余和仍未受控。** 分量数量为线性、幂次总和为三次方预算以内，都不能替代实际标记数的界。局部资源跨分叉复用的问题仍在。

## 24. 不同早端数与轴投影进一步缩小余项

固定宿主交集分量，最短轴周期为 $p$。一个标记子族若只使用至多 $r\ge1$ 个不同早端，其完整早资源有容量
$$
\boxed{C_r=\max\left\{1,\left\lceil\frac{2r}{p+1}\right\rceil\right\}.}
$$
早端不必连续，也不必很早发现；不要求资源是路径或与其平移不交。没有标记时无需分配。

取任意连通子树，只计完整资源包含于其中的标记，令
$$
U\subseteq K,\qquad D=\operatorname{diam}\pi_L(U).
$$
若 $D<p$，同早端的两个源不可能同时出现，因为其投影间距是周期的非零整数倍。于是早端互异，第十三节给单位容量。

若 $D\ge p$，令 $k=\lfloor D/p\rfloor\ge1$。每个早端至多出现 $k+1$ 次；子树包含两个极端投影之间的轴段，故
$$
|U|\ge D+1\ge kp+1,\qquad
\frac{k+1}{kp+1}\le\frac2{p+1}.
$$
最后一个不等式等价于 $(k-1)(p-1)\ge0$。资源数因此不超过 $2r|U|/(p+1)$。逐个资源并的连通分量求和，得到所述容量的 Hall 条件。

特别地，
$$
r\le\left\lfloor\frac{p+1}{2}\right\rfloor\ \Longrightarrow\ C_r=1,\qquad
r\le p+1\ \Longrightarrow\ C_r\le2.
$$
所有满足 $t(e)<p$ 的资源至多使用 $p-1$ 个早端，因而有二容量；周期一时该类为空。这不再要求早资源位于轴上。

另有一个可全局合并的单位容量类：
$$
\operatorname{diam}\pi_L(S_{a,e})=0.
$$
按唯一投影点分组，每组同早端不能重复，给完整资源单位分配。不同组位于不交的轴投影纤维，分配可以直接合并。资源可以完全离轴，也可以在一个轴点处分叉。

### 保持原系数的更小剩余和

沿用第二十三节的临界分量。在每个分量内，令 $r_{h,K}$ 为全部共同切口剩余标记使用的不同早端数。若
$$
2r_{h,K}\le7(p_K+1),
$$
整个分量可用七容量支付。其他临界分量先支付短下标类，再支付单点投影类，合计至多三容量。它们与非临界分量的七容量是按分量作不交分类，因此仍可统一放入原七容量预算。

令 $R_{h,K}$ 只计同时满足下列条件的剩余标记：
$$
2r_{h,K}>7(p_K+1),\qquad
t(e)\ge p_K,\qquad |E(S_{a,e}\cap L)|\ge1.
$$
分量本身仍须满足第二十三节的高幂、分叉及非退化轴交条件。得到
$$
\boxed{W\le(9n-7)N+\sum_{(h,K)\in\mathcal C}R_{h,K}.}
$$
不符合早端数条件的求和项取零。系数没有增加，但末项仍未受控。

## 25. 查询侧周期轴及共同周期的长度预算

以查询根为单位元，查询点的自由群根词记为 $w_x$；宿主源的自由群顶点记为 $a$。固定宿主标签分量的左乘为 $g=u^q$，最短周期为 $p$。真实标记满足
$$
g(a w_e)=a w_f,\qquad
a^{-1}ga=w_f w_e^{-1}.
$$
因此每个早端确定一条查询轴，
$$
I_e=\operatorname{Axis}(w_f w_e^{-1})=a^{-1}L.
$$
它不依赖同早端选择哪个源。同一查询轴类的所有源都把这条轴送到宿主轴。两源之比保持宿主轴，因而是最短轴平移的整数次幂；所有源同行，这一类有单位容量。

完整晚前缀包含从早端到晚端的路径，其中央轴段长度为
$$
|E(P_{t(f)}\cap I_e)|\ge qp.
$$
这里不能把晚前缀换成早前缀。

### 共同周期轴的长度和

设有限 Cayley 子树为 $T$。取不同轴，双向方向词均以同一个正整数 $p$ 为周期，并且
$$
A_I=T\cap I,\qquad |E(A_I)|\ge4p.
$$
则
$$
\boxed{\sum_I|E(A_I)|\le4|T|.}
$$

首先，两条这样的轴若共享连续 $p$ 条边，沿相同方向读取这一整周期便决定两端所有字母。方向边延拓唯一，故两轴相同。

任选树根。每条轴段在最浅点切成两条祖孙段，取较长者，边数记为 $b_I$，于是
$$
b_I\ge\frac{|E(A_I)|}{2}\ge2p.
$$
从较深端取前 $\lfloor b_I/2\rfloor$ 条边及端点，得到闭半段 $H_I$。若两份半段共享一点，从该点向祖先方向，两条原段都还保留至少 $p$ 条边，迫使两轴共享整周期，矛盾。因此这些半段点不交，而
$$
|H_I|=\left\lfloor\frac{b_I}{2}\right\rfloor+1
\ge\frac{|E(A_I)|}{4}.
$$
求和即得长度预算。这里周期长度固定，不能直接把不同周期的轴一起求和。

对固定宿主标签分量，当 $q\ge4$ 时，所有实际查询轴在最终有效查询内各有至少 $qp$ 条边，故
$$
\sum_I|E(Q\cap I)|\le4|Q|,\qquad
\#\{I\}\le\frac{4|Q|}{qp}.
$$
同一轴不能按其多个标记重复计入。

### 跨轴反序给出候选数界

取不同查询轴 $I,J$，固定一笔后者的标记 $(e_J,f_J)$。只考虑曾产生前者标记、且该早端早于 $e_J$ 的不同晚候选源，记为 $\mathcal A$。不同查询轴必来自不同查询交集分量，时间反序给出
$$
t(e)<t(e_J)<t(f_J)<t(f).
$$
每个这样的源都匹配整个 $P_{t(f_J)}$，所以在同一宿主树 $C$ 内留下 $aJ$ 的至少 $qp$ 条轴边。

不同源给出的轴 $aJ$ 不同：若相同，两源之比同时保持 $I,J$；非平凡自由群左乘不能保持两条不同的平移轴。应用刚才的长度预算，得到
$$
\boxed{|\mathcal A|\le\frac{4|C|}{qp}\le\frac{4N}{qp}.}
$$
这只数不同源。同一源可以贡献多个早端，不同查询轴类仍会复用资源，尚不能把该界换成全部标记数。

## 26. 周期轴在实际平面中的延长

本节增加一个抽象自由树没有的几何性质。假设道路已经包含某条周期轴的连续至少两个最短周期，最短周期边数为 $p$，网格位移为非零水平整数向量 $\delta$。第二十三节的临界分量满足这个条件。

### 无限延长仍是诱导网格路径

取一个周期的折线弧 $\alpha$。相邻两个周期已在简单道路路径中，所以 $\alpha$ 与 $\alpha+\delta$ 只共享连接端点。Brouwer 平移弧引理说明，非零平面平移的这种弧不会与非相邻迭代相交：否则会产生固定点指数为一的 Jordan 曲线，而平移的位移场是非零常向量，指数只能为零。[Ortega，Translation arcs and stability in two dimensions，第 3–4 节](https://www.ugr.es/~ecuadif/files/arc.pdf)

于是
$$
\Gamma=\bigcup_{k\in\mathbb Z}(\alpha+k\delta)
$$
是一条无自交的双向折线。基本弧紧致、位移非零，所以两个方向都离开每个有界区域；它把平面分成两侧。平移保持折线方向及平面方向，因此分别保持两侧。

按连续格点下标记为
$$
\lambda_{i+p}=\lambda_i+\delta.
$$
假设有额外单位格边连接不相邻的两个轴点，其下标为 $i<j$。若 $2\le j-i\le p$，整周期平移后两个端点都落在已知的两周期道路段内，与诱导森林矛盾。

若 $j-i>p$，该单位边和它的周期平移在轴上的端点严格交错：
$$
i<i+p<j<j+p.
$$
单位格边的开段不能穿过别的格点边，所以两弦都不碰轴；它们互为平移，处于轴同一侧。两条单位边又平行且端点互异，彼此不交。这违反同侧交错端点弦必相交的 Jordan 分离性质。

所以无限轴的格点仍构成诱导路径。仅从 Cayley 树中的轴，不能跳过上述平面论证。

### 完整交域的轴外部分不会碰到虚拟延长线

仍取有真实标记的完整交域。沿轴选择方向，使
$$
K=C\cap g^{-1}C,\qquad
A=C\cap L=[l,r],\qquad
g\text{ shifts }L\text{ by }\ell>0.
$$
假设一个轴外分量从实际附着点 $\beta$ 出发，首次碰到无限物理轴的下标为 $t$。取这段道路弧及其标签平移。二者都在同一宿主树内，分别附着于 $\beta,\beta+\ell$，属于不同的抽象轴投影纤维，所以点不交。

碰点及其平移都不能在实际轴段内，否则同一道路树内不同抽象点具有同一格坐标。因此
$$
t\notin[l,r],\qquad t+\ell\notin[l,r].
$$
两个附着点都在实际轴段内，故 $r-l\ge\ell$。若碰点在右侧，或者在左侧，分别得到
$$
\beta<\beta+\ell<t<t+\ell,
\qquad\text{or}\qquad
t<t+\ell<\beta<\beta+\ell.
$$
两弧开段均不碰轴，平移使其处于同一侧，交错端点迫使相交，矛盾。故轴外分量确实完整处于无限轴的一侧。

也不存在通向虚拟轴的额外单位邻边。若邻接轴点在实际轴段内，诱导性立即产生环。否则把该单位边接到刚才的道路弧末尾；平移后的邻接点若进入实际轴段，同样成环，若仍在外面则仍是同侧交错端点。单位格边内部不能新增交叉，又得到矛盾。

因此
$$
\boxed{K\cup\Gamma\text{ is an induced grid tree}.}
$$
这是一棵无限树。结论针对完整交域，不能扩大到任意宿主树的轴外部分；两份道路弧同时属于同一宿主树是必要前提。

### 最短周期的几何长度

设基本周期使用 $H$ 个不同行。半开周期内的 $p$ 个顶点，按“行、列对水平位移绝对值取余”映射时不能重合；否则无限轴上两个不同下标会落到同一物理格点。每行只有 $|\delta|$ 个余数，得到
$$
\boxed{p\le H|\delta|\le n|\delta|,\qquad
\ell_g=qp\le H|h|\le n|h|.}
$$
这里位移范数只指水平整数的绝对值，轴长度按边数计。该性质保留了实际网格约束，尚未支付第二十四节的标记余项。

## 27. 按资源左端点分组，将周期容量改为一次系数

固定一个含真实标记的宿主标签分量，以整数坐标表示公共轴，最短周期为 $p$。任取完整早资源的子族，设它们的投影跨度均满足
$$
\operatorname{diam}\pi_L(S)\le B,\qquad B\in\mathbb Z_{\ge0}.
$$
则该子族具有完整资源容量
$$
\boxed{C_B\le1+\left\lceil\frac Bp\right\rceil.}
$$
不要求资源为路径、位于轴上，或与标签平移不交。

记每份资源投影的最小坐标为
$$
\lambda(S)=\min\pi_L(S).
$$
同一早端的两份不同资源由交换标签映射的左乘相互对应。它保持公共轴，并沿轴平移非零整数倍的最短周期；因此两份资源的最小投影也相差非零整数倍的周期。将资源按以下区间分组：
$$
\lambda(S)\in[jp,(j+1)p),\qquad j\in\mathbb Z.
$$
每组早端互异，由第十三节有单位分配。

若某个道路点属于资源，资源左端点只可能位于其投影左侧的有限区间：
$$
z\in S,\quad x=\pi_L(z)
\quad\Longrightarrow\quad \lambda(S)\in[x-B,x].
$$
这个闭整数区间至多遇到
$$
1+\left\lceil\frac Bp\right\rceil
$$
个分组。叠加各组的单位分配即得结论。按资源左端点而非候选源分组，使这里无须同时向左右延长跨度。

共同切口后的资源与标签平移不交，所以
$$
B\le qp-1
\quad\Longrightarrow\quad C_B\le q+1.
$$
这将第二十节的容量改为
$$
\boxed{
\widetilde M_h\le |G_h|+
\sum_{K\in\operatorname{comp}(G_h)}
\min\{1+b(K),\,q_K+1\}|K|.
}
$$
仍只对有剩余标记的分量求和。若相关幂次数统一有界，则有更小的条件界
$$
q_K\le q_0
\quad\Longrightarrow\quad
W\le[(q_0+3)n-(q_0+1)]N.
$$
特别地，
$$
q_0=1\quad\Longrightarrow\quad W\le(4n-2)N.
$$

另一个不要求切口分离的推论是
$$
\operatorname{diam}\pi_L(S)<2p
\quad\Longrightarrow\quad C\le3.
$$
此类包括轴投影为单点及短发现下标的资源，也允许资源本身很大、在轴外任意分叉。

## 28. 长早前缀使不同查询轴在平面中分离

固定同一宿主标签分量及
$$
g=u^q,\qquad q\ge4,\qquad p=\ell_0,\qquad \delta=h/q.
$$
每个查询轴在完整晚前缀中含至少一个标签长度，由第二十六节可延成无限诱导网格路径。取两笔标记，满足
$$
t(e_i)<t(e_j),\qquad I_i\ne I_j,\qquad
|E(P_{t(e_i)}\cap I_i)|\ge2p.
$$
则它们的无限物理查询轴 $\Gamma_i,\Gamma_j$ 不相交，且不存在连接二者的单位格边。

**不相交证明。** 后一笔的完整早资源包含较早前缀的平移像：
$$
a_j+P_{t(e_i)}\subseteq a_j+P_{t(e_j)}\subseteq K.
$$
其中有一段至少两个周期长的较早轴。两条无限轴都以同一水平位移为周期，若相交，交点也按该位移重复。这段实际轴包含两个这样的交点，相隔一个完整轴周期。

第二十六节保证完整交域并上宿主虚拟轴是诱导树。因此这两个交点之间的实际道路只能沿宿主轴连接，不能经过其轴外部分。较早轴的平移像与宿主轴共用一整个周期，由第二十五节迫使两条抽象轴相同。后一源的逆映射随即给出两条查询轴相同，与假设矛盾。

**不格邻接证明。** 若无限轴之间有一条单位格边，按共同周期复制后，较早的实际两周期轴段包含两条这样的连接边的端点。该轴段已与宿主虚拟轴不交；两条连接边、该轴段及虚拟轴上的连接段组成一个环。完整补全是诱导树，所以这些格边必须存在，又不可能形成环，矛盾。

这里必须使用较早的**早前缀**。每笔标记的晚前缀自动具有长轴段，不足以触发本结论。

### 长早前缀轴类的数量

只统计至少有一笔标记的早前缀含两个周期的不同查询轴，记其数为 $k$。按每类第一次满足条件的早端排序，上述结论给出无限物理轴两两不交且互不格邻接。

每轴在最终有效查询中至少含一个标签长度，其实际点集互不相交，所以
$$
\boxed{k(qp+1)\le |Q|.}
$$
若查询树跨越 $H_Q$ 个连续整数行，则每轴一周期的行与列余数键互异，不同轴的键也不相交。因此
$$
\boxed{kp\le H_Q|\delta|.}
$$
每轴完整周期的行范围都已在查询中出现，故没有把虚拟轴新增的行算入这个预算。

还可固定任意一条竖直半整数直线，从每条无限轴选一条跨过它的水平格边。这样的边一定存在，因为非零水平周期使轴向横向两端无限延伸。不同轴所选边的行相差至少二，否则有额外格邻接。所以
$$
\boxed{k\le\left\lceil\frac{H_Q}{2}\right\rceil.}
$$

每个轴类仍有第二十五节的单位容量，但不同类的宿主资源可以相交；以上结论只给出轴类数预算，不能把全部长资源直接视为单位容量。

## 29. 保持容量七，余项至少涉及五类长早轴

每标签仍先用一次交集大小支付共同切口前的部分。固定剩余标记的一个宿主分量，记不同早端数为 $r_{h,K}$，长早前缀轴类数为 $k_{h,K}$。以下任一条件足以用容量七支付全部剩余标记：

- 幂次数至多六，由第二十七节容量界支付。
- 分量为路径，或轴交为单点，使用第二十一、二十三节。
- 早端数满足第二十四节的容量七条件。
- 长早前缀轴类至多四：轴跨度不足两周期的资源用容量三，每个长轴类用容量一。

因此只需保留满足以下条件且交域有分叉、轴交含边的分量：
$$
\mathcal D=
\{(h,K):q_K\ge7,\ k_{h,K}\ge5,\
2r_{h,K}>7(p_K+1),\
K\text{ has a fork},\ |E(K\cap L)|\ge1\}.
$$
在这些分量中，先支付所有短跨度资源，再任选四个长轴类支付；可选标记最多的四类。令未支付的标记数为
$$
R^{(24)}_{h,K}
=\#\{(a,e):\operatorname{diam}\pi_L(S_{a,e})\ge2p_K,\
I_e\text{ is outside the four selected classes}\}.
$$
此处只计共同切口后留下的真实标记。每个分量已付容量仍至多为七，因此
$$
\boxed{
W\le(9n-7)N+\sum_{(h,K)\in\mathcal D}R^{(24)}_{h,K}.
}
$$
新余项包含于第二十四节的旧余项，因为轴跨度至少两周期也保证发现下标足够大及轴交非退化。早端互异、源共线等已有单位容量判据还可继续使用。

**最后的和仍未控制。** 长轴类数可以随实例增长；轴数预算没有消除多类资源在宿主中的重复使用。

## 30. 另一条周期轴使相同轴像中的副本错开

设查询中的两条不同抽象轴具有相同的最短周期水平位移，第一条轴的最短边周期为 $p$，且其无限物理轴已经由第二十六节证明为诱导路径。两个完整前缀映射满足
$$
I\ne J,\qquad aI=bI,\qquad a\ne b,
$$
并且都把一段实际查询轴路径 $A\subseteq J$ 映入同一道路树。则
$$
\boxed{aA\cap bA=\varnothing.}
$$
这里的相交先按实际格点理解。两份已在同一道路树中的副本共点，也就是方向词树中的同一顶点。

相对左乘保持共同轴像，沿轴平移非零整数倍的最短周期，物理位移相应为
$$
\Delta_{\rm grid}=s\delta,\qquad
\Delta_{\rm axis}=sp,\qquad s\in\mathbb Z\setminus\{0\}.
$$
另一条无限物理轴同样以该水平位移为周期，所以两份无限物理轴像重合。若实际有限副本共点，它们在此点的整个双向方向续接一致。Cayley 树从一个顶点按方向续接是唯一的，故两条抽象轴像也相同。相对左乘便同时保持两条不同轴，违背非恒等自由群左乘只有一条平移轴的性质。

若两条查询轴的周期边数也同为 $p$，其有限段副本是在同一无限物理轴上平移相应边数得到的。有限段不交进一步给出
$$
\boxed{|\Delta_{\rm axis}|>|E(A)|.}
$$
在同一宿主标签分量内，同查询轴类的源都满足轴像相同，所以可以直接使用。下一节还允许源属于不同交集分量，只要求所选参考轴像相同。必须保留两源都完整匹配所用轴段的条件。

## 31. 固定共轭类中，轴上早端可以计入参考轴点块

固定一个水平标签及其真实共同切口。沿用第十二节的共同晚前缀和较小早树：
$$
R\subseteq P,\qquad P\cap(R+h)=\varnothing.
$$
每个剩余标记的早端在较小早树中，其晚候选完整匹配共同晚前缀。

将查询侧标签左乘按自由群共轭类分组。同一类的循环约简词只差循环移位，因此最短周期边数、幂次和水平周期位移一致。以下只统计任意一个剩余标记子族中，属于同一共轭类且早端本身在其查询轴上的标记：
$$
q\ge4,\qquad e\in I_e.
$$
这与“早资源包含长轴段”不同；早端可能在轴外，因此并未覆盖所有余项。

### 选择参考标记

取该族最晚的早端及其标记，记参考轴为
$$
(e_*,f_*),\qquad J_*=I_{e_*}.
$$
同一参考查询轴类属于同一查询平移交集分量，按第六节的势能单射，标记可计入互异的宿主交集终点。记这一部分的个数为 $E_{\rm ref}$。

其他轴类属于不同查询交集分量，全局时间反序给出
$$
t(e)<t(e_*)<t(f_*)<t(f).
$$
因此每个非参考源都完整匹配参考晚前缀。该前缀在参考轴上有至少一个标签长度：
$$
|E(P_{t(f_*)}\cap J_*)|\ge qp.
$$

### 每源的标记数与共同点块长度

对每个非参考查询轴取其与共同早树的实际轴交。早端在这个交中，所以它非空。令
$$
B=\max_{I\ne J_*}|E(R\cap I)|.
$$
最大值只取本子族出现的非参考轴；若没有非参考标记，则此后费用为零。由于每条无限物理轴平移一个标签等于沿轴移动一个标签长度，切口不交性给出
$$
0\le B\le qp-1.
$$
否则实际早树中会有两个相差标签的轴点，与切口条件矛盾。

一个固定源只属于一个查询交集分量，所以它的所有这些早端都在同一轴交中；不同标记的早端互异。因此每个非参考源至多贡献
$$
B+1
$$
笔标记。从参考晚轴段固定截取一段 $V$，满足
$$
V\subseteq P_{t(f_*)}\cap J_*,
\qquad |E(V)|=B,\qquad |V|=B+1.
$$
每个非参考源都把这段完整映入宿主。

### 同一轴像中的点块互不相交

将非参考源按其参考轴像分组：
$$
\Lambda=aJ_*.
$$
对同一轴像中的不同两源，取达到最大跨度的非参考轴。两源都完整匹配共同早树，因此第三十节适用，其沿参考轴的相对位移大于共同点块的边数。于是这些点块两两不交：
$$
aJ_*=bJ_*,\quad a\ne b
\quad\Longrightarrow\quad aV\cap bV=\varnothing.
$$
每源的标记数不超过自己点块的顶点数，故可计入该点块。此计费使用道路中的参考晚轴点，**没有断言它们属于原标记的完整早资源**，所以不是新的完整资源 Hall 定理。

设不同实际参考轴像构成集合 $\mathcal A$，每条轴按其道路分量区分。每条轴在相应道路树中至少有一个标签长度，故第二十五节的共同周期打包给出
$$
T_{h,\mathfrak c}
=\sum_{\Lambda\in\mathcal A}|C_\Lambda\cap\Lambda|,
\qquad
M^{\rm on}_{h,\mathfrak c}\le E_{\rm ref}+T_{h,\mathfrak c},
$$
$$
\sum_{\Lambda\in\mathcal A}|E(C_\Lambda\cap\Lambda)|\le4N,\qquad
|\mathcal A|\,qp\le
\sum_{\Lambda\in\mathcal A}|E(C_\Lambda\cap\Lambda)|.
$$
因此
$$
\boxed{T_{h,\mathfrak c}\le4\left(1+\frac1{qp}\right)N\le5N.}
$$

### 不同共轭类仍需共同预算

固定标签时，一个实际宿主轴及其水平周期位移决定标签幂次和共轭类，所以不同共轭类不会重复列出同一个宿主轴。各参考类的终点单射还可以合并：同一宿主交集点的标签左乘唯一，其共轭类也唯一。于是
$$
\boxed{
M_h^{\rm on}\le |G_h|+\sum_{\mathfrak c}T_{h,\mathfrak c}.
}
$$
这里仍只计所选高幂、严格切口、早端在轴上的子族。

不能给每个共轭类重新支付一次整个道路数，就宣称总量线性。不同类可能具有不同最短周期，固定共同周期的长度打包不能直接跨类相加；第二十三节的幂次和界也不是轴长度和界。早端离轴的标记亦未被本节支付。这是一个新的收费归约，一般对数缺口仍然保留。


## 32. 多个重复轴类可以共存于连通资源中

不能进一步假设只有常数多个轴类具有重复早端。有一个显式诱导树族，查询具有 $k$ 条长早轴，上层每个早端出现 $t$ 次，底层还有更多重复；所有完整早资源的并仍连通。参数可取
$$
k\ge2,\quad t\ge1,\quad t(k-1)\ge2,\quad
d\ge10,\quad 5\mid d.
$$
上层候选横坐标按间距 $d+10$ 排列，底层候选每隔五列布置。记
$$
P=(d+10)(t(k-1)-1),\qquad b=P/5+1.
$$
真实标记数、完整资源并点数，以及选取四个最大长轴类时上轮规则留下的数量分别为
$$
\widetilde M_h=3t(k-1)+6b+1,\qquad
|\mathcal U|=b(6k+4)+1,
$$
$$
R^{(24)}_{h,K}=(k-4)t\qquad(k\ge5).
$$
全部标记都有显式单位分配：短齿上的早端计入第一条已访问短齿的对应点；底行额外两相位及末端计入自身终点；离轴小钩也计入自身终点。不同高度、列模五的相位和末端范围使这些分配点互异。

因此该族只排除“重复轴类数量有限”这种简化，不是算法反例。它的查询点数至多为棋盘边长两倍，通用逐前缀界本身已给出
$$
|Q|\le2n,\qquad W\le2nN.
$$
六轴固定例有三百零七笔标记，每类都重复，完整资源并为一千八百四十一点；原程序与独立答案均通过。[参数族证明与显式分配](../examples/repeated-axis-classes.zh.md)保留构造、一般公式和有限检查边界。

## 33. 全部直轴上的早端可以合并支付

第三十一节的固定共轭类界在直轴情形还能加强。最短周期为一且物理位移水平，意味着循环最短词是朝标签方向的一步水平边。因此对固定非零水平标签，
$$
p=1,\qquad q=|h|,
$$
只有一种可能的有向共轭类。

其不同参考轴像与道路的实际交段都是水平直路。若同一道路树中的两条此类轴共用一个实际顶点，按水平边双向唯一续接便强迫它们是同一抽象轴。不同道路分量又没有公共顶点。所以全部不同参考轴像的实际道路点集互不相交，第三十一节的费用改为
$$
T_{h,\rm straight}\le N.
$$
于是，对任意严格切口后的高幂标记子族，只保留直轴且早端在轴上的部分，有
$$
\boxed{M_{h,\rm straight}^{\rm on}\le |G_h|+N.}
$$
不限制查询轴类数、同早端重复数，或资源并的连通性。

有符号水平标签至多有两倍边长减二个。合并全部标签的交集预算后，
$$
\boxed{
\sum_h M_{h,\rm straight}^{\rm on}
\le3(n-1)N.
}
$$
这里无需给每个宿主交集分量重复领取一次道路数预算；同一标签的全部分量已经在第三十一节共同处理。

可将其用于第二十九节的整个未付子族。去除其中所有直轴且早端在轴上的标记，记剩余数量为
$$
R_{\rm curved/off}^{(25)}
=\#\{(h,K,a,e)\text{ in the Section 29 remainder}:
p_K>1\text{ or }a+e\notin L_K\}.
$$
则一般扫描还有严格归约
$$
\boxed{
W\le(12n-10)N+R_{\rm curved/off}^{(25)}.
}
$$
其余旧条件仍保留，包括真实共同切口、高幂、足够多长早轴，以及每份未付资源至少两个周期。这个余项仍未受控，但所有最短周期为一且早端在轴上的标记已经具有合并后的目标量级。

类似地，若只取最短周期边数有固定常数上界的轴上早端，则原始方向字只有有限种共轭类型。第三十一节每类型的费用也能合并成常数倍的目标预算；该常数依赖所选周期上限。一般情形仍需处理增长的弯曲周期类型，以及早端离轴的标记，不能省略这两部分。

## 34. 完整交域不能任意按标签周期延长

第二十六节只保证完整交域与其无限轴之并是诱导树，不能据此同时加入交域的全部标签平移副本。

以下坐标依次为行、列。令向下、向右、向左的单位方向分别用大写字母表示，取
$$
h=(0,10),\qquad
B_{\rm L}=D^2W^2D^3E^2,\qquad
B_{\rm R}=D^2E^2D^3W^2.
$$
两条折线都从原点出发，终点相同，但绕向相反。道路包含零行从零至四十列的水平路，在零、十列接入左折线，在三十、四十列接入右折线。四条枝杈相互分离，因此道路是诱导树。相应交域恰为
$$
K=\{(0,c):0\le c\le30\}\cup B_{\rm L}
  \cup\bigl(B_{\rm R}+(0,30)\bigr),
$$
其中方向词在并集中表示其全部顶点，包括起点。直接有
$$
N=77,\quad |K|=49,\quad p=1,\quad q=10,\quad K\cup(K+h)=F.
$$
然而，左枝杈平移三次后与原右枝杈在三十列对齐，两者围出十四边环。因此
$$
\bigcup_{j=0}^{3}(K+jh)
$$
已经不是森林。

此交域确实承载真实标记。查询先沿轴右行两步再返回，完整访问左枝杈并沿原路返回，然后右行十步，完整访问第二条左枝杈。重新按全部候选计算星心，得到九笔严格切口标记；早端全部离轴，早资源轴跨度都为二。实际参数为
$$
n=45,\quad |Q|=29,\quad m=41,\quad W=228.
$$
原程序和独立答案核验均通过。该查询的活动资源并只有十二点，没有使用右枝杈，所以这个反例没有否定活动资源的更强性质，更不是算法复杂度反例。

## 35. 单份切口资源的全部标签平移仍为诱导森林

与上一节不同，真实切口资源有额外的不交条件。这一节不要求周期幂次大，也不要求早端位于轴上。

### 连通格点集在圆柱上的单射

设有限连通格点集及非零水平整数平移满足
$$
S\cap(S+h)=\varnothing,\qquad h=(0,d),\qquad d>0.
$$
负向标签可通过反射归为此情形。把水平坐标模掉标签长度，得到圆柱投影
$$
\pi_d(r,c)=(r,[c]_d).
$$
则此投影在该格点集上是单射，等价地，
$$
\boxed{(S+ih)\cap(S+jh)=\varnothing\quad(i\ne j).}
$$

证明：若有两点投影相同，先在连通格点集中取连接它们的简单路径，再取该路径上端点投影相同且长度最短的子路径。它在圆柱上的投影是简单闭曲线。单位网格边的内部不会在投影后新增交叉；否则提升回平面就会得到不经过公共格点的网格边相交。

此闭曲线的提升，终点与起点相差非零整数倍的标签。将圆柱与去掉原点的平面对应，绕原点的圈数正是这个整数。但简单闭曲线的绕数只能为零、正一或负一。于是这两个原格点相差一个正向或反向标签，与初始不交性矛盾。这里使用的是 Jordan 曲线的绕数结论，见 [NTNU 讲义第一定理](https://www.math.ntnu.no/emner/TMA4175/2011v/continuousLogs2.pdf)。

标签长度一或二时，圆柱上的网格可能有自环或平行边；应保留它们作为实际嵌入的边，不能把商图擅自简化。这不影响上述简单闭曲线论证。

### 不会跨过一个副本产生额外格邻接

在相同前提下，两个不同副本之间若有单位格边，则副本下标必相邻：
$$
\boxed{
\{x,y+kh\}\text{ is a unit grid edge},\quad x,y\in S,\quad k\ne0
\ \Longrightarrow\ |k|=1.
}
$$
取格点集内连接两端代表点的简单路径。上一段的单射性保证其圆柱投影也是简单路径。加入这条跨副本边，就得到绕数为副本下标差的简单闭曲线，故绝对值只能为一。两端代表点相同时，路径为空，跨副本边自身是简单闭曲线，结论仍成立。

特别地，若第一次平移与原集合之间没有格邻接，则任意两个不同整数倍平移之间都没有格邻接。

### 从两个实际副本推广到全部副本

再假设原格点集本身是诱导树，且它与第一次平移的并是诱导森林。由于两份非空连通树不交，它们之间至多有一条单位边。前两段已排除全部远距离碰撞与邻接，所以
$$
\boxed{\mathcal P_h(S)=\bigcup_{j\in\mathbb Z}(S+jh)
\text{ is an induced grid forest}.}
$$
若第一次平移之间没有边，这些副本是不同分量；若有一条边，则各副本沿整数次序串联，整个并是诱导树。

对真实严格切口标记，
$$
S=a+P_{t(e)},\qquad
S\cap(S+h)=\varnothing,\qquad
S\cup(S+h)\subseteq F.
$$
所以该结论适用于每一份完整早资源。它还适用于一个高幂交域中，固定轴投影点的整个纤维：纤维和第一次标签平移位于不同轴附着点，且两附着点间的轴距离至少为二，故在实际道路树中既不相交也不邻接。该纤维的不同标签副本始终互不相交、互不邻接。

单射性另外给出点数界。若集合覆盖的行数为其高度，则
$$
\boxed{|S|\le H(S)\,d.}
$$
真实共同早树也满足第一次平移不交，所以同样有此点数界。但共同早树的两个平移副本未必同时被一个候选匹配，不能直接对它使用上面的诱导森林结论。

这些结论只控制单份资源的所有平移。不同资源可能重叠，不能据此宣称它们具有单位 Hall 容量，也不能直接把各资源点数相加支付扫描。

## 36. 参考轴类可以连同离轴早端一起支付

第三十一节的参考标记可以从同一共轭类的全部所选高幂严格标记中选取，不必只从早端在轴上的标记中选取。仍选早端发现时间最晚者，参考轴记为
$$
J_*=I_{e_*}.
$$
现在支付所有参考轴类标记，以及其他轴类中早端在轴上的标记。参考类的势能终点单射没有使用早端在轴上的条件。非参考部分仍然满足早端在轴上；对它们，时间反序、每源标记数界和参考晚轴点块证明完全保留。因而
$$
M^{\rm paid}_{h,\mathfrak c}
=\#\{(a,e):I_e=J_*\text{ or }e\in I_e\},
$$
$$
\boxed{
M^{\rm paid}_{h,\mathfrak c}\le E_{\rm ref}+T_{h,\mathfrak c},
\qquad T_{h,\mathfrak c}\le5N.
}
$$
集合只在所选共轭类子族内计数。点块跨度最大值只取确实需要支付的非参考轴上早端所属轴；参考早端离轴，不会改变这些轴交非空的事实。不同共轭类的参考终点仍可联合单射。

对最短周期为一的子族，第三十三节的实际水平轴交互不相交仍给出
$$
\boxed{
M^{\rm paid}_{h,\rm straight}\le |G_h|+N,\qquad
\sum_h M^{\rm paid}_{h,\rm straight}\le3(n-1)N.
}
$$
因此可在同一个费用下，额外去除参考轴类中的全部离轴早端。

具体地，在第二十九节余项内，对每个标签的周期一子族，按上述规则选取参考查询轴。其为空时无需选择。去除所有轴上早端及所选参考轴类后，令余项为
$$
R^{(26)}
=\#\{(h,K,a,e)\text{ in the Section 29 remainder}:
p_K>1\text{ or }(a+e\notin L_K,\ I_e\ne J_{h,*})\}.
$$
参考轴只在周期一分支中使用。严格有
$$
\boxed{
W\le(12n-10)N+R^{(26)},\qquad
R^{(26)}\le R_{\rm curved/off}^{(25)}.
}
$$

其他轴类的离轴早端确实可以存在。一个加入短钩的六轴固定实例有三百一十七笔标记，其中五十六笔离轴。扩大参考类后支付其中四十六笔离轴标记，另外五类各留下两笔。这些标记也各自具有显式单位资源分配，因此该实例仍不是算法反例。


## 37. 共同晚前缀将每源点块扩大到一个标签长度

固定一个水平标签、真实共同切口和一个高幂共轭类的任意严格标记子族。沿用第三十六节最晚早端的参考标记及参考查询轴。记标签沿轴的长度为
$$
\ell=qp,\qquad q\ge4,\qquad J_*=I_{e_*}.
$$
参考查询轴类仍可全部计入互异的宿主交集终点。以下只讨论其他轴类，允许早端离轴。

### 所有非参考源共享一份更晚的完整前缀

若非参考子族非空，从中选取晚端发现时间最早的标记：
$$
(a_\dagger,e_\dagger,f_\dagger),\qquad
t_\dagger=\min_{\rm nonref}t(f),\qquad I_\dagger=I_{e_\dagger}\ne J_*.
$$
每个非参考源至少对应一笔标记，其晚端时间不小于这个最小值，因此该源完整匹配此前缀。参考标记与非参考标记的时间反序同时给出
$$
t(f_*)<t_\dagger,\qquad
a+P_{t_\dagger}\subseteq F\quad\text{for every nonreference source }a.
$$
这个共同晚前缀在第二条查询轴上含有至少一个完整标签长度。令
$$
A=P_{t_\dagger}\cap I_\dagger,\qquad |E(A)|\ge\ell.
$$

将这些源按实际参考轴像分组。若两个不同源具有同一道路树中的相同参考轴像，则第三十节适用于这个共同完整轴段：
$$
aJ_*=bJ_*,\quad a\ne b
\quad\Longrightarrow\quad
|\Delta_{\rm axis}|>|E(A)|\ge\ell.
$$
这里不要求两源自身的标记属于同一查询轴类。所用条件是两源确实匹配同一个第二轴段，且第二轴不同于参考轴。

### 一个点块可以支付任意早端

参考晚前缀在参考轴上也至少有一个标签长度。从中固定截取
$$
V\subseteq P_{t(f_*)}\cap J_*,
\qquad |E(V)|=\ell,\qquad |V|=\ell+1.
$$
每个非参考源都完整匹配它。同一实际参考轴像中的点块，由上一段的间距两两不交。

若每源有若干笔非参考标记，可任取不超过点块点数的标记计入该块。记每源数量及不同实际参考轴像的道路点数和分别为
$$
r_a=\#\{\text{selected nonreference markers with source }a\},\qquad
T_{h,\mathfrak c}=\sum_{\Lambda\in\mathcal A}|C_\Lambda\cap\Lambda|.
$$
则
$$
\boxed{
\sum_a\min\{r_a,\ell+1\}\le
|\{\text{nonreference sources}\}|(\ell+1)
\le T_{h,\mathfrak c}\le5N.
}
$$
参考类另按交集终点支付。早端可以在任意轴外位置，因而比第三十六节只支付非参考轴上早端更强。

这个新规则保留全部旧付款：同一源的轴上早端互异，且都在共同早树与其查询轴的交段中；切口不交性使该交段至多有一个标签长度个顶点。因此先保留所有轴上早端，再将点块剩余位置用于离轴早端即可。

费用仍使用实际参考晚轴点，未要求它们属于原早资源，所以没有宣称完整资源内的 Hall 容量。

### 同像内的完整共同早树副本不交

上述间距还给出一个独立的几何结论。共同早树在参考轴上的投影跨度满足
$$
\operatorname{diam}\pi_{J_*}(R)\le\ell-1.
$$
若早树不交该轴，其投影是一个点；若相交，其投影就是实际轴交段，跨度受切口不交性限制。两源的相对轴位移大于一个标签长度，故两份投影区间不交。在道路树上轴投影唯一，于是
$$
\boxed{
aJ_*=bJ_*,\quad a\ne b
\quad\Longrightarrow\quad
(a+R)\cap(b+R)=\varnothing
}
$$
对这里的非参考源成立。不同实际参考轴像之间仍可能复用道路枝杈，不能将这些完整副本并跨轴像直接求和，替代前面的轴点预算。

## 38. 直轴余项只需继续控制每源超额

最短周期为一时，固定标签只有一个共轭类；不同实际参考轴的道路交点集互不相交。因此上一节的点块费用至多为道路点数。参考类与各源的点块付款，仍可以按第三十三节合并到原有全标签预算。

将该规则用于第二十九节原余项。令其全部弯曲周期标记数为
$$
R_{\rm curved}^{(24)}
=\#\{(h,K,a,e)\text{ in the Section 29 remainder}:p_K>1\}.
$$
对每个标签的周期一子族，按最晚早端规则选取参考查询轴；参考类整体支付。其余每源的标记数记为
$$
r_{h,a}.
$$
空子族无需选择参考轴，参考类的源不进入以下内部求和。则
$$
R^{(27)}
=R_{\rm curved}^{(24)}
+\sum_h\sum_a\bigl(r_{h,a}-(|h|+1)\bigr)_+,
$$
$$
\boxed{
W\le(12n-10)N+R^{(27)},\qquad
R^{(27)}\le R^{(26)}.
}
$$
两轮比较使用相同的第二十九节余项和参考规则，并优先支付旧规则已经支付的轴上标记。新余项仍未受控，但周期一部分不再需要统计全部非参考离轴端点，只剩每源超出点块容量的部分。

### 超额不能直接省略

将第三十六节六轴例的钩深改为二十、相邻查询轴行距改为二十三，可得到一个满足正式范围的指定输入：
$$
n=274,\quad N=16808,\quad |Q|=504,\quad m=1030,\quad W=325690.
$$
它有一千三百八十一笔严格标记，早端离轴的一千一百二十笔。完整高幂严格族中，参考类有一千一百五十一笔，其他十个源各有二十三笔，而每源点块容量十六。

此例还按第二十九节实际筛选：六个长早轴类中，底层一千零五十九笔，上层每类四十二笔。支付四个最大类后留下两个类，共八十四笔。在这份余项内重新选择参考类，先支付四十二笔；另一类的两个源各有二十一笔，点块各支付十六笔，最终仍留下十笔。

这十笔也有显式单位资源分配：同候选的第一条已访问深钩提供对应深度的不同点。全部标记的完整分配、真实星心、诱导森林、原程序与独立答案检查均通过。因此该例说明超额确实存在，没有否定算法复杂度。


## 39. 跨参考轴像的完整资源求和仍会无界高估

第三十七节证明同像内的完整早树副本不交，但跨像求和不能因此直接计入道路数。即使先支付四个最大长轴类和参考类，只统计剩余源实际用到的最大早资源，这个求和仍可比道路数多一个无界因子。

### 嵌套梳状构造

取
$$
k\ge6,\quad t\ge1,\quad w\ge3,\quad
D=6w,\quad R=D+3,\quad s=2w+5,\quad d=3s,\quad h=(0,d),
$$
$$
B=2w^2+6w,\qquad b=5(t-1)+1.
$$
每条梳向下延伸给定深度，每隔三行挂一条给定宽度的横齿；其非根点数就是上式中的梳大小。

查询逐层下行，在每层右二处完整访问右梳。最底层先在一个相位处访问左梳，再在相差一个标签处访问另一条左梳；随后自下而上，把各上层横臂延至标签加二处并访问右梳。各段均返回主竖干，最后回到原点。

上层源位于
$$
a_{i,j}=(-iR,5sj),\quad 1\le i<k,\quad0\le j<t;
$$
底层源位于
$$
(-kR,c),\quad c\in\{0,s,\ldots,5s(t-1)\}.
$$
对上层源，指定早端是对应层右梳的最后齿端；对底层源，是第一条特殊左梳的最后齿端。晚端为早端加标签。道路取各源的完整晚前缀与标签平移源的完整早前缀之并。

展开道路并集，负行是相位列上的主竖干及每层短右梳；零行把它们连在一起并挂特殊左梳；正行按每五个相位的列组分开，每组有主竖干、长横臂及左右交替的梳。右梳齿和下一左梳齿的最近端点相隔三列；相邻层的梳也相隔三行。列组之间隔一个相位。所有连接都发生在指定根或共用竖干上，没有额外四邻接边，故道路是诱导树。

负行有轴类数乘列组数量级的互不交完整梳；整个道路分解只有同阶片段，得到
$$
N=\Theta(ktB),\qquad
n=\max\{(2k-1)R+D+1,\ (5t-1)s+1\},
$$
$$
|Q|=1+kR+kd+2(k-1)+s+(2k+1)B,\qquad
m=2|Q|-2+4k.
$$

初始整行距下行及右二迫使有关候选从相位列、整层行开始；完成最初主竖干又迫使上层源属于指定列组。标签平移源不能在正行再下行一整层，所以它只对应自身层的早端。负行没有长横臂，又排除了更前层的晚端。

同行更早的梳点若要遮盖星心，会把源移到非相位列；左右梳齿的相位区间分离也排除了互相遮盖。底层轴点按列模相位分组，只有最右源保留第一条特殊梳根的额外星心。完整真实标记数为
$$
\widetilde M_h=(k-1)t(B+3)+b(B+s)+1.
$$
所有标记都通过严格共同切口，且最短周期一。上层每类的长早资源标记数为每源梳大小加一；底层最大。支付底层及最下面三个上层类后，再选余项中的最晚早端类为参考，得到
$$
R^{(24)}=(k-4)t(B+1),\qquad
R^{(27)}=(k-5)t(B-d)=(k-5)t(2w^2-15).
$$
等大类按先支付较晚层处理，是第二十九节允许的一种选择。

### 粗求和的无界因子

非参考源还剩前面若干层。各源的最大实际早资源大小和为
$$
\sum_{i=1}^{k-5}\sum_{j=0}^{t-1}|S^{\max}_{i,j}|
=t\left((k-5)+(R+2+B)\frac{(k-5)(k-4)}2\right)
=\Theta(tk^2B).
$$
各源的参考轴像行不同；同一行不同列组的实际水平臂不连通，在宿主树中的轴像也不同。因此先按参考轴像取资源并，仍是这个求和。它与道路数的比值随轴类数增长；第三十七节的同像内不交性并未失效。

全部标记仍有单位分配：上层标记移到同源首次访问的短臂或右梳对应点，底层前三个轴点同样处理，其他底层点用自身早端像。不同层高度带、不同列组及左右梳相位区间排除碰撞。

完成初始下行右转后只剩轴类数乘列组数量级的候选；这些候选中的指定源又全部通过最初梳状阶段。因此
$$
W=\Theta(k^2tB).
$$
特别地，
$$
k=t=w\to\infty:\qquad
N=\Theta(n^2),\quad
\sum|S^{\max}_{i,j}|=\Theta(n^{5/2}),\quad
W=\Theta(n^{5/2}),\quad m=\Theta(n^{3/2}).
$$
这否定粗资源预算，未否定目标复杂度。道路分解、真实星心排除及分配的逐项证明见[参数证明](../examples/nested-combs.zh.md)。

## 40. 非参考源的标签平移必须在参考早端前失效

固定同一标签、真实共同切口和一个高幂共轭类的所选子族，仍按最晚早端选择参考标记。任取非参考源，则
$$
a+P_{t(f_*)}\subseteq F,\qquad
a+h+P_{t(e_*)}\not\subseteq F.
$$
第一式由时间反序成立。证明第二式只需反证：若平移源也完整匹配参考早前缀，则
$$
a+P_{t(e_*)}\subseteq G_h.
$$
这棵连通前缀包含该源，故全部位于它原来的标签分量。该分量上统一的平移词于是也把参考早端像送到参考晚端像；拉回查询树后，非参考轴类与参考轴类的平移词相同，矛盾。

因此可为每个非参考源定义标签平移候选的第一次失败下标：
$$
j_a=\min\{j:a+h+q_j\notin F\}.
$$
对于该源的全部所选标记，
$$
\max_{e\ {\rm at}\ a}t(e)<j_a\le t(e_*).
$$
晚源仍成功匹配这段。设失败查询点的父点是它在发现树中的唯一更早邻点，则有一条真实道路边
$$
x=a+\operatorname{parent}(q_{j_a})\in K,\qquad
y=a+q_{j_a}\in F\setminus G_h.
$$
它为每个非参考源提供一条离开标签交域的边。后续已证明，同一条边即使在现有付款之后，仍可承载线性多个剩余源及无界超额。因此不能直接按边常数收费；完整参数证明见[十轮研究第 1 节](reference-followup.zh.md)。

删除参考类后的连通资源不交猜想现已被左右早横枝反例否定；反例仍有互异早端，因此没有否定单位容量本身。构造及替代的容量二证明稿见[续研记录](reference-capacity.zh.md)。后续审计将其关键步骤改为有限第二轴引理，移除高幂限制并完成[一般三次方证明](cubic-bound.zh.md)；有限分配检查作为补充验证单独保存。

此前的[轴投影等价引理](reference-followup.zh.md)将不交性精确改写为连通资源的轴投影跨度小于标签轴长，并证明原顺序嵌套梳满足该性质。该引理和限定族结论保留，一般的严格短跨度命题已被上述反例否定。