题解：P5334 [JSOI2019] 节日庆典

_zhuhy_ · 2026-03-07 20:34:31 · 题解

定义 SUF 为以后有可能成为答案的后缀。

结论1：SUF 为另一个比它长的 SUF 的前缀。

证明：考虑两个 SUF x,y，其中 |x|<|y|，那么 x 和 y 在前 |x| 位就能比较出谁大，所以有一个不可能成为答案。

结论2：对于相邻两个 SUF，记为 x,y，且 |x|<|y|，那么 |y| \geq 2|x|。

证明：反证，若 |y| < 2|x|，根据结论1，x 是 y 的前缀，那么 x 可以表示为 AB，y 表示为 AAB，记后面的加入的串为 r，那么若 x 是答案，xr<yr，即 ABr<AABr，x 消掉，即 Br<ABr，即此时存在更小的 B 比 x 更优。

引理：根据结论2，进一步的观察到 SUF 最多只有 \mathcal{O(\log n)} 个。

于是考虑维护 SUF，假设当前的 SUF 为 q_1,q_2,\dots,q_m，且 q_1>q_2>\dots>q_m。

此时加入 c 字符，将 c 加入 q_m 所在的位记为 pos，那么将 c 与 q_{m-1} 的 pos 位（记为 c'）进行比较。

那么现在的 SUF 都是互为前缀的，接下来要使它们满足 2 倍关系。

即从最大长度 SUF 开始，如果下一个串不满足，则淘汰掉下一个串，然后接下去循环即可。

然后接下来的问题是如何快速比较两个循环的大小。

考虑两个开始的位置分别为 x,y，且 x<y。

将其分成三个部分比较。

那么比较这一块的时间复杂度为 \mathcal{O(1)}。

预处理 Z函数 的时间复杂度为 \mathcal{O(n)}。

维护 SUF 的时间复杂度为 \mathcal{O(n\log n)}。

总时间复杂度为 \mathcal{O(n\log n)}。

提交记录 link