CSP2025 T3 题解

前言

唉，

思路

设询问串为 $(s,t)$，给定的串为 $(a,b)$。

证明一个 $(a,b)$ 对一个 $(s,t)$ 的贡献最多为 $1$ 是平凡的，询问即对 $(s,t)$ 计算有多少个满足条件的 $(a,b)$。

设 $l=\min_{s_i≠t_i}\{i\},r=\max_{s_i≠t_i}\{i\}$，记 $f(x,y)=(x[l\cdots r],y[l\cdots r])$，$L(x,y)$ 为 $x$ 和 $y$ 扣掉 $f(x,y)$ 之后剩下的左边的子串（由定义，这两个串是同一个串），$R(x,y)$ 为右边的（同理）。则 $(a,b)$ 对 $(s,t)$ 的贡献是 $1$，当且仅当 $f(a,b)=f(s,t)$，$L(a,b)$ 是 $L(s,t)$ 的后缀，$R(a,b)$ 是 $R(s,t)$ 的前缀。

因为 $f$ 只需要判是否等于，开局先对所有二元组 $f$ 哈希。看到前后缀匹配，可以使用 Trie。在 Trie 上，$x$ 是 $y$ 的前缀相当于 $y$ 对应的节点在 $x$ 对应的节点子树内，如果对字符串按其在 Trie 中对应点子树内的 dfs 序区间标号，可以表示成 $l_x\leq l_y\leq r_x$。那么分别对前面定义的所有 $L(a,b),L(s,t)$ 和 $R(a,b),R(s,t)$ 这样标号，就变成了普通的三维偏序且一维限制是等号的问题，可以用动态开点线段树维护每种 $f$，$\mathcal{O}(n\log n)$ 解决。但其实我们如果不对 $R$ 显式标号，把动态开点线段树换成对 $R$ 建 $n$ 棵 $f$ 值不同的动态开点 Trie，在扫描线每次查询时统计从第 $f$ 棵动态开点 Trie 的根到查询的 $R(s,t)$ 对应节点路径上的点的贡献，这部分除去离散化就可以做到线性（实际上也可以上 trie 求 $f$ 的 dfs 序去掉离散化的 log 并且摆脱哈希，但是没啥必要）。

总复杂度 $\mathcal{O}(\sum |S|+n \log n)$，精细实现后 $\mathcal{O}(\sum |S|+n)$。

yjh 提醒我遍历 trie 求 dfs 序复杂度多了个字符集。当然可以对 trie 每个点开个链表来解决这个问题，但是太蛋疼了，可以考虑对每个点的邻接矩阵压位模拟链表，插入、删除、遍历都可以使用位运算解决。