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

## 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$ 包含且仅包含下列整数格点：

1. 左竖干 $x=0,-8\le y\le8$。
2. 三根下垂干 $x=7,20,27$，均为 $-8\le y\le0$。
3. 在 $y=-8,-4$ 两行，从每根 $x=0,7,20,27$ 的干向右伸两格短齿。
4. 横路 $y=0,0\le x\le29$。
5. 横路 $y=4,0\le x\le27$。
6. 五个叶子
   $$
   (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](inputs/connected-resources.in)

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