[Str记录]Loj#6070. 「2017 山东一轮集训 Day4」基因

· · 个人记录

题意 ： 给出一个字符串 s ，每次询问某个子串的本质不同回文子串数。

强制在线，|s|\leq 10^5,q\leq 2\times 10^5 ，时限\texttt{2s}。

旧文分档。请配合 回文自动机小记 食用。

咕。

先考虑所有询问的 r=|S| 的情况。

此时，一个回文子串能贡献当且仅当其最靠后的出现(起始)位置 t 满足 l\leq t。

设 B[i] 为此时在 i 最后一次开头的回文串个数，那么询问 [l,|S|] 的答案就是 B[l,|S|] 的和。

再来考虑一般情况怎么离线做。

从小到大增大 r ，逐个加入字符，不断更新 B。考虑新加入一个字符之后，会给 B 带来什么影响。

不难发现，终止链上的所有串都能够在结尾处出现，这比它们之前的出现都要靠后。

所以，对这些串，我们需要在 S 上的若干位置(上一次出现的位置)减一，然后在若干位置(新出现的位置)加一。

其中一个等差序列的情况如图 :

空心紫圈表示减一，实心紫圈表示加一。

不难发现，中间的大部分加减都抵消了，只剩下对红串(等差数列中最长串)上一次出现的 -1 ，和等差链顶的 +1.

等差链顶容易求，可是红串的上一次出现位置我们并不能直接求出。

每次新增一个字符，就会使得终止链上所有串的最后出现被更新。只需要对红串的子树内前缀结尾点编号求个 \max 即可，可以用 dfs 序线段树维护。

若需要强制在线，将维护 B 的数据结构更换成主席树即可。

时空复杂度均为 O(n\log^2n) ，常数较小。

Loj评测记录