CSP2025 T3 题解

M1rai · 2025-11-02 00:34:04 · 题解

前言

blog

唉，

思路

设询问串为 (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 每个点开个链表来解决这个问题，但是太蛋疼了，可以考虑对每个点的邻接矩阵压位模拟链表，插入、删除、遍历都可以使用位运算解决。