连通完整资源中的多类型与重复早端¶

1. 结论¶

存在一个合法诱导道路树和真实查询，在固定水平标签下同时满足：

出现两个实际查询面积势能类型。
三个查询早端分别被两笔标记使用。
全部完整早前缀资源 \(S=a+P_e\) 的并集连通。
更强地，有一笔标记的资源与其他每笔资源共享顶点，因此资源相交图本身连通。

这否定了关于实际资源连通分量的分离猜想：不能按实际资源并集的连通分量，把标记一概分成“单类型”或“早点不重复”两类。

它没有否定完整前缀单位 Hall。本例的 14 笔标记有显式单位分配。这里只核验下面一个预定构造，没有参数扫描或随机搜索。

项目	值
方框边长 \(n\)	30
道路点数 \(N\)	118
查询点数	60
真实行走长度 \(m\)	126
候选扫描数 \(W\)	421
标签	\(h=(20,0)\)
全部该标签真实标记	14
实际查询势能类型（行、列约定）	160、320
完整资源并集点数	31

2. 明确坐标与诱导树¶

以下使用 \((x,y)\) 坐标。势能数值使用行、列坐标的行列式约定。

道路 \(F\) 包含且仅包含下列整数格点：

左竖干 \(x=0,-8\le y\le8\)。
三根下垂干 \(x=7,20,27\)，均为 \(-8\le y\le0\)。
在 \(y=-8,-4\) 两行，从每根 \(x=0,7,20,27\) 的干向右伸两格短齿。
横路 \(y=0,0\le x\le29\)。
横路 \(y=4,0\le x\le27\)。
五个叶子
\[ (7,1),(14,1),(27,1),(7,5),(27,5). \]

四竖干仅沿 \(y=0\) 相连；负高度短齿之间有空列。\(y=4\) 的横路只通过左干连接到其余道路。五个新增点都恰有一个道路邻居：齿行距为四，所以它们不会桥接相邻长横路。因此道路是诱导树。

逐段去重计数为

\[ N=17+3\cdot9+(30-4)+2\cdot4\cdot2+(28-1)+5=118. \]

查询 \(Q\) 是左干 \(x=0,0\le y\le8\)，横齿 \(y=4,0\le x\le22\)、\(y=8,0\le x\le27\)，以及两个叶子 \((7,9),(27,9)\)。它也是诱导树，点数

\[ |Q|=9+22+27+2=60. \]

3. 实际访问顺序¶

根为 \((0,0)\)。下列每段均逐格行走；\(N,S,E,W\) 分别表示上下右左。

\[ \begin{aligned} &N^4E^2W^2\ N^4E^2W^2,\\ &E^7NS\ E^{20}NSW^{27},\\ &S^4E^{22}W^{22}S^4. \end{aligned} \]

第一段依次访问两条短齿。第二段在最高查询行先长到 \(x=7\)，向上首次访问

\[ e_*=(7,9), \]

返回后继续横走到 \(x=27\)，再向上访问

\[ f_*=(27,9)=e_*+h. \]

途中 \(x=20,21,22\) 正是旧最高齿标记的晚端。最后一段完成较低横齿并回到根。

行走长度为

\[ m=16+58+52=126. \]

平移候选 \(a_1=(0,-4)\) 容纳最终完整查询：两条查询齿落在道路的 \(y=0,4\)，两个叶子落在 \((7,5),(27,5)\)。因此全程存在完整合法参考。

4. 原来的两种类型及重复早端仍真实¶

旧标记为

\[ e_{ij}=(j,4i),\quad f_{ij}=(20+j,4i),\quad a_i=(0,-4i),\quad i=1,2,\quad j=0,1,2. \]

最高齿另有重复候选

\[ a'=(7,-8),\qquad c'=a'+h=(27,-8), \]

产生同样三个早端 \(e_{2j}\) 的三笔标记。

完整前缀中新增内容的作用如下。

对最高齿旧晚候选 \(a_2=(0,-8)\)，新早叶 \((7,9)\) 映为 \((7,1)\)。
对重复晚候选 \(a'\)，它映为 \((14,1)\)。这正是不能省掉的第五个道路叶子；它保证旧最高齿的三个晚端到达时，候选仍匹配整个此前前缀。
对较低齿晚候选 \(a_1\)，最高横齿的加长部分落在延长后的 \(y=4\) 横路，两个查询叶子落在 \((7,5),(27,5)\)。

旧早候选仍只需相应短齿阶段的完整前缀。任何更早同行点 \(x<j\) 若要命中同一目标，候选横坐标将进入右短齿内部，而非竖干；其第一向上步落在不存在的道路上。因此旧九笔仍由真正最早星心产生。

这里 \(j=0\) 的早端是 \((0,4i)\)，不是查询根，不涉及被排除的根星心。

5. 新连接标记及四笔附带标记¶

5.1 连接标记¶

取

\[ a_*=(0,-8),\qquad c_*=a_*+h=(20,-8). \]

在 \(e_*=(7,9)\) 时，\(c_*\) 的整个早前缀落在右竖干、\(y=-4\) 的短齿、\(y=0\) 的横路和叶子 \((27,1)\) 中。在 \(f_*=(27,9)\) 时，\(a_*\) 的整个晚前缀落在左竖干、下方短齿、\(y=0\) 的完整横路，以及叶子 \((7,1),(27,1)\) 中。

两者都命中目标 \((27,1)\)。\(e_*\) 是查询行 \(y=9\) 中首次发现的点，所以它确实是该目标在此行的最早星心，没有借用任意端点配对。

5.2 最高齿中间四点也是真实标记¶

当最高早段长到 \(j=3,4,5,6\) 时，旧早候选 \((20,-8)\) 仍合法。稍后查询到达 \(20+j\)，晚候选 \((0,-8)\) 也仍合法。这又给出四笔标记

\[ (j,8)\longrightarrow(20+j,8),\qquad j=3,4,5,6. \]

更早同行点只能要求横坐标在 \(21,\ldots,26\) 的候选；这些位置的第一向上步都不存在。到 \(j=7\) 时情况改变：更早的非根点 \((0,8)\) 已由候选 \((27,-8)\) 命中目标 \((27,0)\)，所以 \((7,8)\) 不再是星心。程序按完整定义重建，确认本标签的全部标记恰为

\[ 6+3+4+1=14. \]

6. 同一个真实资源相交分量中的混合¶

旧六笔的资源并集是一个 13 点短梳 \(T\)：左干 \(x=0,-8\le y\le0\)，以及 \(y=-4,0\) 上向右两格的短齿。三笔重复标记的资源并集是 \(T+(7,0)\)，也有 13 点。

连接标记的完整早前缀资源为

\[ S_*=T\cup\{(3,0),(4,0),(5,0),(6,0),(7,0),(7,1)\}. \]

它包含旧六笔的资源，与每一笔重复标记的资源都共享 \((7,0)\)。四笔附带标记的资源也包含在 \(S_*\) 内。因此连接标记的资源与其余每笔资源共享顶点，资源相交图有以它为中心的 13 边生成星。

资源并集大小为

\[ |T\cup(T+(7,0))\cup S_*|=13+13+6-1=31. \]

两个实际势能类型也没有被合并：较低齿的类型为 160，最高齿和连接标记的类型为 320，数值使用行、列行列式约定。连接标记虽在新行 \(y=9\)，其两端的查询路径先回到 \(y=8\) 横齿再横走，因此势能类型与最高齿相同。

于是，同一实际资源相交分量中既有两种类型，也有三个重复早端。这比单纯在 \(G_h\) 中用未访问道路连接资源更强。

7. 仍有显式单位分配¶

本例不反驳完整早前缀 Hall，可以如下收费：

旧六笔 \((i,j)\) 分配到 \((j,4-4i)\)。
三笔重复最高齿标记分配到 \((7+j,-4)\)。
四笔附带标记分配到 \((j,0)\)，\(j=3,4,5,6\)。
连接标记分配到 \((7,1)\)。

这 14 个道路点互不相同，且逐笔位于各自完整早前缀内。所以被否定的是“按类型或早端是否重复进行简单分类”的充分条件，不是单位 Hall 本身，更不是原算法的复杂度界。

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

代表性输入¶

connected-resources.in

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