# 催化序列题解

**出题人解法：按最小间距分治，配合滑动窗口与八叉位树。** Codex（GPT-6）整理证明与 C++17 实现，显式处理长度一和分层度零，不改变核心算法。

## 1. 大间距只能出现在短区间

设 $U=\max a_i$ ，取阈值 $T=\lfloor\sqrt U\rfloor+1$ .如果区间分层度大于 $T$ ，区间元素互不相同。把它们从小到大排列，相邻元素至少相差 $T+1$ ，所以长度不超过

$$1+\left\lfloor\frac{U-1}{T+1}\right\rfloor$$

枚举每个左端点，向右插入元素，维护当前最小间距。一旦间距不大于 $T$ 就停止。因此每个起点只需处理 $O(U/T+1)$ 个元素。

向有序集合插入 $x$ 时，新出现的最小间距只可能来自 $x$ 与它的前驱或后继。若集合已有 $x$ ，新间距就是零。对每个长度至少二的区间，按其实际间距更新答案；刚使间距降到阈值以下的区间也可以记录。

同时为每个右端点 $r$ 记录分层度大于 $T$ 时最靠左的起点 $L_{T+1}(r)$ .为统一记号，单元素区间视为满足任意间距下界，但不能更新最终答案。

## 2. 小间距用滑动窗口

对 $d=T,T-1,\ldots,1$ ，从左到右计算 $L_d(r)$ ：这是以 $r$ 结尾、所有数对差的绝对值都至少为 $d$ 的最长窗口的左端点。

插入新元素前，如果它与当前窗口的前驱或后继距离小于 $d$ ，就从窗口左端删除一个元素，直到可以插入。删除元素不会使已有数对产生更小间距，因此这个过程给出最靠左的合法起点。左右指针各移动至多 $n$ 次。

关键是要求间距**恰好**为 $d$ .由于 $L_d(r)\le L_{d+1}(r)$ ：

- 若严格小于，以 $L_d(r)$ 开头的窗口满足下界 $d$ ，却不满足下界 $d+1$ .数值为整数，所以其最小间距恰为 $d$ ，用其长度更新答案。
- 若相等，这个最长窗口已经满足下界 $d+1$ .它的任何后缀也满足，因而以 $r$ 结尾不存在最小间距恰为 $d$ 的窗口。

一个数组即可从 $L_{T+1}$ 逐轮覆盖成 $L_T,L_{T-1},\ldots$ .严格变小也保证更新的是长度至少二的区间。

分层度为零时，只要全序列有重复值，整个序列就是最长答案；否则答案为零。

## 3. 八叉位树

用一棵完整八叉树表示整数值域。每个内部节点用八位掩码记录哪些儿子的子树非空，另记录每个值是否存在。插入、删除沿路径更新掩码；查找前驱或后继时，先向上寻找相邻非空分支，再沿最右或最左分支下降。预计算八位掩码的首、末非零位位置。

本题 $U\le250000$ ，可用 $8^6$ 个叶子覆盖。一般而言树高为 $O(\log(U+1))$ ，一次操作耗时同阶，空间为 $O(U)$ .所有正阈值窗口中的值互不相同，因此不需要用多重集合维护计数。

## 正确性与复杂度

间距大于阈值的所有合法区间都在短区间枚举中出现；小间距由上述左端点严格变化判据完整识别；零间距单独处理。这三类覆盖所有可能答案，且每次更新对应一个真实合法区间，故结果正确。

时间为 $O(n(T+U/T+1)\log(U+1)+U)$ ，取所述阈值后为 $O(n\sqrt U\log(U+1)+U)$ .空间为 $O(n+U)$ .

`std.cpp` 保留八叉位树；换用平衡树不会改善渐进复杂度，但节点分配与指针访问会改变常数，部署时应实测。

## 使用与验证

编译 `std.cpp` 后，用 `python tests/generate.py --out-dir <目录> --std <程序路径>` 生成数据及答案。`tests/plan.json` 覆盖单点、重复、交替、等距、排列和随机序列。独立校验直接枚举区间内全部数对。参考时限见[评测环境与性能](../../../docs/评测环境与性能.md)。