「区间本质不同回文子串」题解

题意简化

给定字符串 $s$，多次询问区间 $[l, r]$ 内本质不同回文子串的数量。 $n \le 10^5$，$q \le 2n$，可能强制在线。

核心算法：回文树 + 扫描线

1. 回文树

回文树（回文自动机）能 $O(n)$ 处理所有本质不同回文串：

• 每个节点代表一个本质不同回文串
• 节点数 $O(n)$

2. 问题转化

对于每个回文串节点 $p$（长度 $len_p$），设其在原串中的出现位置集合为 $pos_p$。

节点 $p$ 对询问 $[l, r]$ 有贡献当且仅当：

$$\exists i \in pos_p,\quad l \le i \le r - len_p + 1 $$

即：至少有一个完整出现落在 $[l, r]$ 内。

3. 离线算法（$\text{type}=0$）

将所有询问按右端点 $r$ 排序，扫描右端点。

维护每个节点 $p$ 的最后出现位置 $last_p$。

当扫描到位置 $i$ 时（$s[i]$ 是当前右端点）：

• 更新回文树，记录新出现的回文串
• 对于每个新出现的回文串节点 $p$，更新 $last_p = i$

对于询问 $[l, r]$，节点 $p$ 有贡献当且仅当：

$$last_p - len_p + 1 \ge l$$

树状数组维护：

• 每个节点 $p$ 在位置 $last_p - len_p + 1$ 上 +1
• 当 $last_p$ 更新时，原位置 -1，新位置 +1
• 查询 $[l, r]$：求 $[l, r]$ 区间和

复杂度：$O((n+q)\log n)$

4. 在线算法（$\text{type}=1$）

需要可持久化数据结构。

主席树方法： 对每个右端点 $r$ 建立版本：

• 版本 $r$ 包含所有满足 $last_p - len_p + 1 \le r$ 的节点 $p$
• 节点 $p$ 在位置 $last_p - len_p + 1$ 上标记

查询 $[l, r]$：

• 在版本 $r$ 上查询 $[l, r]$ 区间内的标记数
• 即为答案

为什么正确： 节点 $p$ 在版本 $r$ 中被标记当且仅当：

1. 它在位置 $\le r$ 出现过
2. 它的有效左端点 $\le r$

查询 $[l, r]$ 时，我们只关心有效左端点 $\ge l$ 的节点。

算法步骤

预处理：

1. 建立回文树
2. 扫描字符串，记录每个节点的出现位置
3. 建立主席树：对每个位置 $i$，更新涉及的回文串节点

查询：

1. 根据 $\text{type}$ 和 $\text{lastAns}$ 计算真正的 $l, r$
2. 在主席树版本 $r$ 上查询区间 $[l, r]$ 的和
3. 输出答案，更新 $\text{lastAns}$

复杂度

• 回文树：$O(n)$
• 主席树：$O(n\log n)$ 空间，$O(\log n)$ 查询
• 总复杂度：$O((n+q)\log n)$

关键点

1. 回文树更新

每次添加字符时，回文树会新增若干节点，需要及时更新这些节点的 $last$ 值。

2. 有效左端点

节点 $p$ 在位置 $i$ 出现时，有效左端点为 $i - len_p + 1$。

3. 去重处理

同一节点可能多次出现，我们只关心最后一次出现（最近的 $last_p$）。

4. 强制在线

需要异或处理，但算法本身支持在线查询。

样例解析

字符串：abbabbba

建立回文树后，节点及其出现位置：

• a: 位置 1,4
• b: 位置 2,3,5,6,7,8
• bb: 位置 3-4,6-7,7-8
• bab: 位置 3-5
• 等

查询 $[1,7]$：

• 版本7包含所有有效左端点 ≤7 的节点
• 查询 $[1,7]$ 得到7个节点

代码实现要点

1. 回文树模板
2. 主席树模板
3. 扫描更新逻辑
4. 在线解码逻辑

这种解法能处理 $n=10^5$，$q=2\times 10^5$ 的数据。