GitHub 源文件 Markdown

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

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

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