# 一个道路点可以参与无界多个轴带

## 1. 结论与范围

下面的合法参数族满足：全部资源 $S=a+P_e$ 都与 $S+h$ 不交，但一个道路点参与的不同轴带数随参数增长。因此固定实例中的最大参与数 2 不能推广成一般常数。

甚至按轴带分别取资源并集再把大小相加，也不能保证是 $O(|G_h|)$。本例中该总和为二次量，而 $|G_h|$ 只有一次量。

它仍有明确的单位 Hall 分配，且候选扫描数为 $\Theta(nN)$。它不反驳一般单位 Hall，也不反驳原算法复杂度界。

## 2. 道路、查询和真实行走

使用 $(x,y)$ 坐标，取偶数 $s\ge4$，令 $h=(2s,0)$。

道路 $F$ 为底轴

$$
y=0,\quad 0\le x\le5s,
$$

以及所有叶子

$$
(x,1),\quad x=s,s+2,\ldots,5s.
$$

上叶隔一空格，各只有一个道路邻居。因此 $F$ 是诱导梳形树，

$$
N=(5s+1)+(2s+1)=7s+2,
\qquad n=5s+1.
$$

查询根为零，实际走法是

$$
E^s\ N\ S\ E^{2s}\ N.
$$

因此

$$
e=(s,1),\qquad f=(3s,1)=e+h,
\qquad m=3s+3.
$$

查询最终包含底轴 $0\le x\le3s$ 和两个上叶，点数也是 $3s+3$。候选零点一直存活，实际最终存活候选为 $(j,0)$，其中 $j=0,2,\ldots,2s$。

## 3. 选定新行子族：完整前缀与最早星心

对每个偶数 $j\in[0,2s]$，取

$$
a_j=(j,0),\qquad c_j=a_j+h=(j+2s,0).
$$

早候选 $c_j$ 的完整前缀是底轴 $[j+2s,j+3s]$ 及叶子 $(j+3s,1)$，都在 $F$ 中。晚候选 $a_j$ 的完整前缀是底轴 $[j,j+3s]$ 及两叶 $(j+s,1),(j+3s,1)$，也都存在。

因为 $e$ 是查询行 $y=1$ 中首个被发现的点，它就是对应目标 $(j+3s,1)$ 的真正最早星心。该子族共有 $s+1$ 笔，其完整资源为

$$
S_j=\{(x,0):j\le x\le j+s\}\cup\{(j+s,1)\},
\qquad |S_j|=s+2.
$$

资源横向范围与其 $2s$ 平移严格分离，故 $S_j\cap(S_j+h)=\varnothing$。

## 4. 根所在行还贡献另一批标记

不能把上节 $s+1$ 笔误报成固定标签的全部标记。查询根所在行的最早非根点是

$$
e_0=(1,0),\qquad f_0=(2s+1,0)=e_0+h.
$$

发现晚端时，查询已经访问叶子 $(s,1)$。因此晚候选为偶数源 $(j,0)$，其中

$$
0\le j\le3s-2.
$$

这给出另外 $3s/2$ 笔标记，资源只是 $\{(j,0),(j+1,0)\}$，也与其标签平移不交。$e_0$ 是真正的非根查询点，查询根本身没有被计作星心。

两个查询行各只有上述可能的固定标签配对，所以全部标记精确为

$$
\boxed{M_h=\frac{5s}{2}+1.}
$$

## 5. 带参与数和逐带资源总量

宿主交集恰为底轴 $0\le x\le3s$ 及偶数 $x\in[s,3s]$ 的上叶，故

$$
|G_h|=(3s+1)+(s+1)=4s+2.
$$

以底轴左端作自由群树根，平移词为

$$
g=E^{2s},\qquad \ell_g=2s,\qquad\ell_0=1,\qquad q=2s.
$$

轴坐标就是横坐标。源 $a_j$ 位于第 $j$ 个半开单位带。在道路点 $z=(s,0)$ 处，选定子族恰有

$$
j=0,2,\ldots,s
$$

这些不同带的资源经过。因此

$$
\boxed{\#\{\text{参与 }z\text{ 的带}\}=s/2+1.}
$$

这也是全部标记中的最大逐点带参与数。选定长资源在任意轴点覆盖至多 $s/2+1$ 个偶数源；新增的根行短资源只在 $x>2s+1$ 时带来额外带，此时长资源最多覆盖 $s/2$ 个带，所以总数仍不超过 $s/2+1$。上叶只属于一个长资源。

只对新行子族分别取每带资源并集，其大小和已经是

$$
(s+1)(s+2)=\Theta(s^2).
$$

计入根行后，偶数源 $j\le2s$ 的两笔资源嵌套，带并集仍为 $S_j$；额外偶数源 $j=2s+2,\ldots,3s-2$ 各有两个资源点。因此全部带并集的精确总和为

$$
\boxed{\sum_{\text{带 }b}\left|\bigcup_{a\text{ 在带 }b}S_{a,e}\right|
=(s+1)(s+2)+s-2=s^2+4s.}
$$

它除以 $|G_h|$ 的比值渐近为 $s/4$，无统一常数上界。即使每个带内已有单位分配，也不能通过直接相加各带完整资源大小来免费消除带数。

## 6. Hall 与实际扫描数仍然很小

所有源在同一水平轴上，所有标记属于同一查询势能类型。显式单位分配可取每笔标记的资源终点：

- 根行标记分配到 $(j+1,0)$。
- 新行标记分配到 $(j+s,1)$。

这些点逐笔在自身资源内且互不相同。分带资源可以高度重复，并不意味着实际收费必须重复。

按查询四个扫描阶段精确计数：

| 阶段 | 候选扫描数 |
|---|---:|
| 首段 $E^s$ | $(9s^2+7s+2)/2$ |
| 首个上叶 | $4s+1$ |
| 后段 $E^{2s}$ | $3s^2+2s$ |
| 最后上叶 | $s+1$ |

回到已访问底轴点的那一步不扫描。因此

$$
\boxed{W=\frac{15s^2+21s+6}{2}=\Theta(nN).}
$$

## 8. 向多类型反例推进时的具体限制

仅改变宿主、保留本查询，不能把该标签变成多类型难例：

$$
Q\cap(Q-h)
=\{(x,0):0\le x\le s\}\cup\{(s,1)\}
$$

始终连通，所以查询势能类型只有一个，已有终点注入直接支付全部标记。这是查询本身的限制，不能靠给宿主加叶子消除。

若希望把本例的带拥挤与非共线、多类型源结合，必须改变查询几何，使标签交集出现不同势能类型，并继续保留各源的完整前缀。当前的轴带拥挤不构成 Hall 反例。

参数族的渐近结论针对允许规模增长的数学模型；用于运行正式程序的输入仍须满足题面限制。

## 代表性输入

[overlapping-bands-s4.in](inputs/overlapping-bands-s4.in)

使用 [verify_examples.py](../verify_examples.py) 检查道路森林、移动、候选数与候选检查次数。有限输入只用于复核，不替代上面的参数证明。