题解 | #Spirit Circle Observation#

B Spirit Circle Observation 接着_wfx大佬提出的第一个做法讲讲我个人赛时的做法。这个做法被构造数据卡掉，主要问题是如果每次不停地走9和0可能会被卡到 $O (n)$ 。我在赛时没有考虑去证明这个暴力是否存在一个比 $O (n^{2})$ 低的上界，而是在想这样一件事：如果某一次我暴力走走了很多步，那就意味着存在一段很长的形如9999999999...的子段.规定一个阈值B，在SAM上只能走B步，这样可以把所有后缀9的个数小于等于B的字符串对的贡献都统计到。对于后缀9的个数多于B的，与官方题解中的关键点定义相近，只是规定后缀9的个数大于B才能成为关键点。可以发现这时关键点个数不超过 $O(\frac{n}{B})$ ，暴力枚举关键点点对，每个点对求出两个前缀的最长公共后缀x，对于答案的贡献就是x*(min(后缀9的个数，后缀0的个数)-B)。两个前缀的最长公共后缀对应到SAM上就是前缀在parent树上定位后lca节点的len。总复杂度：

O(|\Sigma|(nB+\frac{n^2}{B^2}\log n))

令前后相等：

B=\sqrt[3]{n \log n} \\ 复杂度： O(|\Sigma|n\sqrt[3]{n \log n})

而官方的标准做法是考虑对于所有长度，关键点个数不超过n，因为一个9或者0只可能对关键点个数创造1的贡献，其他数字也是如此。枚举长度，我们需要求每对关键点的两个前缀的最长公共后缀。还是转化成lca的len，在lca处统计所有儿子的子树中两类关键点的数量，算出以该节点为lca的关键点对数。把每种长度对应的关键点放在SAM的parent树上做个虚树就行，复杂度 $O(|\Sigma|n)$ 。