CF1098F 1log 做法

chenxinyang2006 · 2026-09-09 17:56:35 · 题解

用 lcp(i,j) 代表 s[i,n] 和 s[j,n] 的最长公共前缀。

原问题的答案可以写成 \sum\limits_{i=l}^r lcp(l,i)-\sum\limits_{s[l,i] 是 s[l,r] 的 \text{border}} lcp(i+1,r+1)，考虑分别算前后两项。

前一项的计算是简单的：建立后缀树后借助两个后缀的 LCP 就是它们在后缀树上 LCA 的 len 的性质，这直接变为 经典题，离线后变为 n 次链加 \Theta(q) 次链求和，这部分容易在 \Theta((n+q) \log n) 内计算（LCT/点分治/全局平衡二叉树……）。

对于后一项，考虑应用基本子串字典，每次考虑 s[l,r] 所有长度在 [2^i,2^{i+1}) 内的 border 的贡献，相关理论告诉我们这些 border 的长度构成等差数列， 且设最短的一个 border 是 B，这个等差数列有 k+1 项，存在一个字符串 A 使得第 i+1 短的 border 恰好是 BA^i。

（如果你暂时忘了 border 理论，设这些 border 中最长的一个是 C，现在我们在考虑它所有长度 \ge \dfrac{|C|}{2} 的 border。根据弱周期引理，这些 border 都是由 C 最短周期的整数倍产生的，于是我们找到最短周期对应的后缀是 A，那么 C 就是一段 A 的后缀拼接上 A 完整出现若干次。长度 \ge \dfrac{|C|}{2} 的 border 就是在 C 基础上去掉后面的若干个 A，在满足 [2^i,2^{i+1}) 长度限制的前提下，设最长的一个去掉了 k 个 A，就对应了 BA^i 的形式）

容易理解，这个 border group 的贡献就是，算一些 lcp(*,r+1) 之和，* 是一个等差数列。设这个等差数列最大一项是 p，公差为 d=|A|，要算的是 \sum\limits_{i=0}^k lcp(p-id,r+1)。（注意这里的 p 是 BA^k 这个最长 border 作为 s[l,i] 出现时的下一个位置，即在这个语境下 p=i+1）

因为现在要考虑 s[p-id,n] 的形态：i 每增大 1 会向前添加 d 个字符，由这个 border group 都是 BA^i 的形式，实际上添加的这 d 个字符正是 A，换言之 \forall i \in [1,k],s[p-id,p-id+d)=A。

从而现在的目标是：初始两个串分别是 s[p,n] 和 s[r+1,n]，每次向 s[p,n] 前添加一个 A，重复 k 次，把所有时刻两个串的 LCP 加起来。

若 k=0，则是平凡的，下面设 k>0，且设 h=lcp(p-d,p)。我们的想法是：借助 A^{\infty} 作为桥梁，利用 lcp(s[p-id,n],A^{\infty}) 以及 lcp(s[r+1,n],A^{\infty}) 的信息试图得到 lcp(p-id,r+1)。

关键观察：只要 lcp(s[p-id,n],A^{\infty}) 和 lcp(s[r+1,n],A^{\infty}) 不相等，则 lcp(p-id,r+1) 立刻是它们中的较小值。

证明：指出这点之后，是显然的。

进一步，可以得到：lcp(s[p-id,n],A^{\infty})=h+id。

证明：先考虑 i=0，此时性质描述的是 lcp(s[p,n],A^{\infty})=h，这可以由 h 的定义得出：它是 s[p,n] 以及 A+s[p,n] 的 LCP。而对于 i>0，s[p-id,n]=A^i+s[p,n]，性质当然成立。

设 H=lcp(s[r+1,n],A^{\infty})，这几乎表明 lcp(p-id,r+1) 就是 \min(h+id,H)：只需特判 h+id=H 的唯一一个可能的 i。

于是只需考虑如何得到 H：例如先求一次 lcp(p-d,r+1) 看是否 \ge d，若是则 s[r+1,n] 至少有一个 A 作为前缀，则 H=lcp(r+1,r+d+1)+d，否则 H=lcp(p-d,r+1)。

从而对这个 border group，只需要求 \Theta(1) 次 LCP 即可算出 \sum\limits_{i=0}^k lcp(p-id,r+1)，其余处理也都是 \Theta(1) 的。

而基本子串字典也可以做到 \Theta(n \log n) 预处理 \Theta(\log n) 查询，而第二部分也做到了 \Theta((n+q) \log n)，整道题在 \Theta((n+q) \log n) 时间内解决。

然而跑到最优解需要一些卡常（由 GPT 完成），在算法层面的优化是：

• 前面的链加链求和选用了点分治求解。
• 第二部分的计算可以分类讨论减少一些常数：设 x=lcp(p,r+1)，只要 x \neq h，则 \forall i \ge 1,lcp(p-id,r+1)=\min(x,h)。因为只是用来卡常，理由就不在这里展开了。

加了第二个卡常后的代码，没有加的版本。

在 24 年 5 月我读到了 一道类似题 的 zhouhuanyi 的 1log 题解，让我深受震撼：毕竟原题看上去就是要 2log 才能做的样子，结果分类讨论/容斥之类的搞一搞，再用点 border 理论就 1log 了。读完之后我决定反思一下，是不是有别的以前觉得只能 2log 的字符串题，其实有类似的做到 1log 的方法呢？于是我尝试了若干题目，然后发现 CF1098F 确实可以做到 \Theta((n+q) \log n)！

但代码看上去并不好写。这个做法需要同时写 SAM/基本子串字典/1log链加链和，最后还有一些分类讨论。我当时并没搞清楚过 1log 链加链和到底怎么好写还快，也并不知道怎么写出快的基本子串字典（其实我都没搞清楚过怎么写出复杂度正确的 1log 版本）。当然我可以去找对应的最优解代码然后拼起来，但看懂别人的代码还是有点太麻烦了，于是我懒得搞，干脆就搁置了下来。

中间我告诉过一个学弟这个做法让他去写，但显然他也懒得写，应该也是 24 年的事。

又过了很久了，现在是 26 年 9 月，9.5 GPT6-astra 发布了，我决定测测它的能力。我又想起了这个被我搁置已久的 1log 做法，但我已经忘记做法的细节，而且当初也没有实现过，于是最初我直接丢给 astra 题面和这篇题解的前两行，觉得是不是这差不多也够让它做出来了。

然后它想了 10min 告诉我 “证据不足”，我想是不是 prompt 输的不对，于是进一步描述说虽然说明很简略，但要求是沿着这个路线探索得到 \Theta((n+q)\log n) 做法。

然后它又跑了 10min 告诉我做不出来。

带着中转站是不是掺水了或者被 OpenAI 风控了这根本不是 astra 的怀疑，这次我把类似题的题面和题解丢给了它，然后它想了 40min 总算告诉我现在做法对了，又写了 10min 代码通过了，后面让它卡了 20min 常数获得了 CF 最优解。

总之 AI 很牛，确实节省了让我验证这个想法的时间。至于牛到我没有什么想法值得验证之后怎么办，再说。