催化序列题解¶

出题人解法：按最小间距分治，配合滑动窗口与八叉位树。 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)\) .为统一记号，单元素区间视为满足任意间距下界，但不能更新最终答案。

对 \(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\) .严格变小也保证更新的是长度至少二的区间。

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

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

本题 \(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 覆盖单点、重复、交替、等距、排列和随机序列。独立校验直接枚举区间内全部数对。参考时限见评测环境与性能。