# 正交双梳与粗势能预算

## 1. 结论与范围

令查询和宿主为同一棵诱导网格树 `Q=F`，定义两种面积势能类型预算

```text
B_H = Σ_{d≠0} κ_{Q,(0,d)} |G_{F,(0,d)}|，
B_V = Σ_{d≠0} κ_{Q,(d,0)} |G_{F,(d,0)}|。
```

下面构造一个参数族 `k≥2`，满足

```text
n=4k+5，             N=4k²+10k+9，
B_H=6k⁴+32k³+64k²+58k+20，
B_V=6k⁴+28k³+48k²+40k+20。
```

因此两种预算均为 `Θ(n⁴)`，并且

```text
min(B_H,B_V)/(nN)=B_V/(nN) ∼ 3k/8 → ∞。
```

这严格否定了对所有查询、宿主以 `min(B_H,B_V)=O(nN)` 结束证明的路线。它没有否定面积势能上界本身，也没有构成原候选算法的复杂度反例。

数值核验只取预先指定的 `k=2,3,4`，没有随机搜索或扩大参数。结论来自下面的一般构造与计数，不由三个点拟合多项式。

## 2. 单树坐标和诱导性

使用 `(行,列)` 坐标，令 `b=2k+4`。第一把梳子为

```text
A = {(y,0):0≤y≤2k}
    ∪ {(2i,x):0≤i≤k, 0≤x≤2k}。
```

它有竖直主干和 `k+1` 条长度 `2k` 的向右横齿。

第二把梳子为

```text
B = {(b,x):b≤x≤4k+4}
    ∪ {(y,b+2i):0≤i≤k, b≤y≤4k+4}。
```

它有水平主干和 `k+1` 条长度 `2k` 的向下竖齿。

用以下折线路径连接两把梳子的端点：

```text
(2k,0) → (b,0) → (b,b)，
```

每段包含全部整数格点。取这三部分的并为 `F`，并令 `Q=F`、查询根为 `(0,0)`。

两把梳子各自是诱导树：平行齿之间留有一整空行或空列。连接路径只在第一把梳子的底端和第二把梳子的左端接入；其水平段与第一把梳子的底齿相隔四行，其竖直段又在第二把梳子以左至少 `b` 列。没有额外四邻接。因此并集是一棵诱导树，只有指定连接，不产生环。

每把梳子点数为

```text
(2k+1)+(k+1)·2k=2k²+4k+1。
```

连接路径长 `2k+8`，两个端点已经在梳子内，所以新增 `2k+7` 个点。于是

```text
N=2(2k²+4k+1)+(2k+7)=4k²+10k+9。
```

行、列范围都为 `0,...,4k+4`，故最小方框边长为 `n=4k+5`。宿主恰有 `2k` 个度三点，没有更高度点。

## 3. 仅用直齿已经足以得到四次方下界

对正水平标签 `h=(0,d)`，一段水平直路所在行是 `y` 时，其沿边势能差为 `dy`，而 `det(h,z)=-dy`，所以

```text
c_h(z)=2dy。
```

第一把梳子的 `k+1` 条横齿位于不同的偶数行。对于每个 `1≤d≤k`，每条齿都提供至少 `2k-d+1≥k+1` 个交集点，且这些行给出 `k+1` 个不同势能值。因此

```text
κ_{Q,(0,d)}≥k+1，
|G_{F,(0,d)}|≥(k+1)(2k-d+1)≥(k+1)²。
```

第二把梳子在竖直标签下完全对称：竖直直路的势能值为 `-2d x`，不同齿列给出不同值。

所以两种方向都各有 `Θ(k)=Θ(n)` 个标签，使势能类型数至少 `Θ(n)`、重叠点数至少 `Θ(n²)`。计入正负方向，得到简单的共同下界

```text
B_H,B_V ≥ 2(k+1)² Σ_{d=1}^k(2k-d+1)
        = k(3k+1)(k+1)² = Ω(k⁴)。
```

单凭这一一般下界及 `nN=Θ(k³)`，就已足以否定取两方向较小预算的 `O(nN)` 猜想。接下来给出完整精确计数，确认两者也是 `O(k⁴)`。

## 4. 水平方向的精确类型和交集

只需计算正位移 `d`：负位移的交集是对应平移，势能值整体取负，因此交集大小和不同值个数相同。

### 4.1 势能类型

当 `1≤d≤2k` 时：

- 第一把梳子保留 `k+1` 条互不连接的水平交集，每条在行 `2i`，势能值为 `4di`；
- 连接横路与第二把梳子的水平主干组成一条完整长横路。它的交集，加上可能存在的交集竖齿，仍是一个分量，势能值为 `2d(2k+4)`；
- 中间只有一个道路点的连接竖段各行，不会产生非零水平交集，不能把这两个区域连起来。

上述 `k+2` 个值互不相同。因此

```text
κ_H(d)=k+2，                         1≤d≤2k。
```

当 `2k<d≤4k+4` 时，只剩长连接横路的交集，故 `κ_H(d)=1`；更大的位移交集为空。

### 4.2 交集大小

对于 `1≤d≤2k`，按三种点来源计数：

```text
|G_H(d)| = (k+1)(2k-d+1)
           +(4k+5-d)
           +1_{d为偶数}·2k(k+1-d/2)。
```

第一项来自第一把梳子的横齿，第二项来自长连接横路，第三项来自第二把梳子在主干以下的竖齿重叠。竖齿列相隔二，奇数位移不能使它们重叠。

对于 `2k<d≤4k+4`，仅有

```text
|G_H(d)|=4k+5-d。
```

这些分类按行完全覆盖宿主，且不重计主干。求和得

```text
Σ_{d=1}^{2k}|G_H(d)|=3k³+10k²+10k，
Σ_{d=2k+1}^{4k+4}|G_H(d)|=(2k+4)(2k+5)/2。
```

因此

```text
B_H=2(k+2)(3k³+10k²+10k)+(2k+4)(2k+5)
   =6k⁴+32k³+64k²+58k+20。
```

## 5. 竖直方向的精确类型和交集

### 5.1 势能类型

当 `1≤d≤2k` 时：

- 第一把梳子及连接部分的交集始终通过列 0 上的连续竖段连接，构成一个势能值为零的分量；
- 第二把梳子的 `k+1` 根竖齿分别留下一个互不连接的竖直交集，所在列为 `2k+4+2i`，势能值为 `-2d(2k+4+2i)`。

这些值也互不相同。因此 `κ_V(d)=k+2`。

当 `2k<d≤2k+4` 时，第二把梳子的交集消失，只剩经列 0 连接的一个分量，故 `κ_V(d)=1`。再大的竖直位移无交集。

### 5.2 交集大小

对于 `1≤d≤2k`，精确计数为

```text
|G_V(d)| = (k+1)(2k-d+1)
           +(2k+5-d)
           +1_{d为偶数}·2k(k+1-d/2)
           +1_{d为偶数且d≥4}·2k。
```

四项依次是：第二把梳子的竖齿、列 0 的长连续竖段、第一把梳子的横齿之间重叠，以及第一把梳子某条横齿与连接横路之间的重叠。最后一项的起点是 `d=4`，因为第一把梳子最下齿与连接横路相隔四行，不能误从 `d=2` 开始计。

对于 `2k<d≤2k+4`，仅剩

```text
|G_V(d)|=(2k+5-d)+1_{d为偶数}·2k。
```

所有非列 0 的上述交集横段都接入列 0 的连续交集，因此确实只有第 5.1 节所列类型，没有由孤立段引入漏掉的势能值。

求和得到

```text
Σ_{d=1}^{2k}|G_V(d)|=3k³+8k²+8k，
Σ_{d=2k+1}^{2k+4}|G_V(d)|=4k+10。
```

所以

```text
B_V=2(k+2)(3k³+8k²+8k)+2(4k+10)
   =6k⁴+28k³+48k²+40k+20。
```

两式相减为

```text
B_H-B_V=4k³+16k²+18k>0。
```

故取方向较小值后，仍保留 `6k⁴` 的首项。

## 7. 对后续证明的限制

问题不在于选择了不合适的单一方向：两把正交梳子分别让一个方向出现大量势能类型，并同时提供大交集，旋转取较小值也不能解决。

势能预算将某标签的全部查询势能类型数乘以整个宿主交集大小，允许把并非实际发生的类型与道路资源重复相乘。后续若沿势能方法继续，需要保留真实标记使用的类型、分量或候选信息；单独用最终 `Q,F` 的这两个粗乘积结束证明不可行。

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