CF917E Upside Down

· · 题解

cnblogs

我永远喜欢数据结构。

大家好，我喜欢暴力数据结构，所以使用分块通过了此题。

--- **[洛谷题目传送门](https://www.luogu.com.cn/problem/CF917E)** **[CodeForces 题目传送门](https://codeforces.com/problemset/problem/917/E)** > - 给出 $n$ 个点的树，第 $i$ 条边上有字母 $c_i$。有 $m$ 个字符串 $s_1\sim s_m$ 以及 $q$ 组询问。每次询问给出 $x,y,k$。 > > - 记 $\text{str}(x,y)$ 为 $x,y$ 简单有向路径边上的字母按顺序拼接得到的字符串，形式化地，若 $x,y$ 简单有向路径上一共有 $E$ 条边，记 $e_i$ 为 $x,y$ 有向路径上的第 $i$ 条边，则 $\text{str}(x,y)=\overline{c_{e_1}c_{e_2}\dots c_{e_E}}$。 > > - 求 $s_k$ 在 $\text{str}(x,y)$ 中出现了多少次。形式化地，求有多少个正整数 $i\in[1,|str(x,y)|-|s_k|+1]$ 使得 $\forall\,j\in[0,|s_k|-1]\cap \mathbb{Z},(s_k)_{i+j}=[\text{str}(x,y)]_{i+j}$。 > > - 记 $M=\sum\limits_{i=1}^m |s_i|$，$n,m,M,q\le 10^5$。 > > - $\text{3 s / 512 MB}$。 约定： - 本文中所有下标均从 $1$ 开始。钦定 $1$ 为根。用打印机字体（`\texttt`）表示具体的字符 / 字符串。 - 默认 $\mathcal{O}(n)=\mathcal{O}(m)=\mathcal{O}(M)=\mathcal{O}(q)$，$\mathcal{O}(\sqrt{n})>\mathcal{O}\left(\log^2 n\right)$。 - 记一个点 $u$ 的父亲为 $\text{fa}_u$，深度（到根的边数）为 $\text{dep}_u$。 - $x\rightsquigarrow y$ 表示 $x$ 到 $y$ 的简单有向路径，$u\longleftrightarrow \text{fa}_u$ 这条边上的字符为 $\text{val}_u$。特别地，$\text{val}_1=\texttt{1}$。 - $\text{lca}(x,y)$ 表示 $x,y$ 两点的最近公共祖先。$\text{lcp}(x,y)$ 表示两个字符串 $x,y$ 的最长公共前缀。 - 记一个串 $s$ 的反串为 $s^R$。形式化地，$\left|s^R\right|=|s|$ 且 $s^R_i=s_{|s|-i+1}$。 - $\text{anc}(k,x)$ 表示 $x$ 向上走 $k$ 条边到达的点，即 $x$ 的树上 $k$ 级祖先。 - 若字符参与运算，则其值等于其 $\text{ASCII}$ 值。 --- 考虑弱化版 [CF1045J](https://www.luogu.com.cn/problem/CF1045J) 的做法，$s_k$ 出现的位置要么**完全包含在** $x\rightsquigarrow \text{lca}(x,y)$ 和 $\text{lca}(x,y)\rightsquigarrow y$ 两条直链内，要么跨过了 $\text{lca}(x,y)$。 **$\bf{Case\space1}$：完全包含在直链内的情况** 在这部分中考虑使用哈希实现字符串匹配。我们的哈希方式为多项式哈希，即对于字符串 $s$，其哈希值为： $$H(s)=\sum\limits_{i=1}^{|s|}\left(s_i\cdot \text{base}^{|s|-i}\right)\bmod \text{MOD}$$ 其中 $\text{base}$ 为乘数，$\text{MOD}$ 为模数。本题卡乘数和模数，我使用了【】生日的日期做乘数，$10^9+9$ 做模数。不能自然溢出，因为后面需要用到逆元。 在弱化版中，我们运用 $|S|\le 100$ 的条件，对于每一种长度的字符串单独处理。在此题中我们也可以如法炮制，需要运用到一个引理： > $\bf{Lemma\space 1}

在字符串总长度为 n 的长为 m 的字符串序列 s_1\sim s_m 中，本质不同的字符串长度种数为 \mathcal{O}(\sqrt{n}) 级别。

\bf{Proof\space 1}

考虑 s_1\sim s_m 种出现了 k 种本质不同的长度，从小到大依次是 \text{len}_1\sim \text{len}_k，记 \text{cnt}_i 表示第 i 种长度的出现次数，形式化地，\text{cnt}_i=\sum\limits_{j=1}^m[|s_j|=\text{len}_i]。

那么有：\sum\limits_{i=1}^k(\text{len}_i\cdot \text{cnt}_i)=n。

可以发现 \text{len}_i\ge i,\text{cnt}_i\ge 1。后面那个很显然，因为这种长度出现时一定存在一个字符串满足其长度为 \text{len}_i。

至于前面那个使用归纳法证明：

  • 当 i=1 时 \text{len}_1\ge 1 显然成立。

  • 假设对于 i\in[1,p]\cap\mathbb{Z} 时成立，则对于 i\in[1,p+1]\cap\mathbb{Z} 时，由于 \text{len}_1\sim \text{len}_k 中的每一个数都是一种本质不同的长度，且从小到大排列，所以 \text{len}_{p+1}>\text{len}_p\ge p。由于都是整数，所以 \text{len}_{p+1}\ge p+1。

由于这里涉及到的量都是正的，所以 \text{len}_i\cdot \text{cnt}_i\ge i，因此 \sum\limits_{i=1}^ki\le \sum\limits_{i=1}^k(\text{len}_i\cdot \text{cnt}_i)=n，因此有 \dfrac{k^2+k}{2}\le n。可以得到 k\le \sqrt{2n}=\mathcal{O}(\sqrt{n})。注意这里不是在解不等式，由 \dfrac{k^2+k}{2}\le n 推导出一个成立的条件。

证毕。

那么我们可以对于这 \mathcal{O}(\sqrt{n}) 种长度分别求解。在求解一种长度 \text{len} 的询问时，我们对于每个点 u 预处理 \text{str}(u,\text{anc}(\text{len},u)) 和 \text{str}(\text{anc}(\text{len},u),u) 的哈希值 \text{uk}_u 和 \text{dk}_u（若不存在则不处理）。需要先预处理 \text{up}_u 和 \text{dwn}_u 表示 \text{str}(u,1) 和 \text{str}(1,u) 的哈希值。容易得到：

由于这个做法比较垃圾，我们不能在求解每种长度时重新遍历树计算哈希值，否则会超时。可以考虑牺牲空间，在第一次遍历树时就对于每个点存下这些哈希值。这样可以省去 \mathcal{O}(\sqrt{n}) 次遍历树的时间。

具体地： - $\text{uk}_u\equiv \dfrac{\text{up}_u-\text{up}_{\text{anc}(\text{len},u)}}{\text{base}^{\text{dep}_u-\text{len}}}\pmod{\text{MOD}}

可以预处理 \text{base} 的若干次方以及对应的逆元。考虑怎么快速求 \text{anc}(\text{len},u)。由于查询次数为 \mathcal{O}(n\sqrt{n})，所以单次查询必须为 \mathcal{O}(1)。可以考虑维护 1\rightsquigarrow u 构成的序列 \text{stk}，使得 \text{stk}_i 为路径上的第 i 个点。则所求即为 \text{stk}_{\text{dep}_u-\text{len}}。每次遍历到一个点 u 时，将 u 加入序列末尾。结束 u 的遍历时，将 u 从序列末尾删除。

在求解每种长度时再考虑对于每种询问串的哈希值 \text{hsh} 单独求解。考虑记 \text{num}_{0,u} 表示 1\rightsquigarrow u 上有多少个点 v 满足 \text{uk}_v=\text{hsh}，\text{num}_{1,u} 表示 1\rightsquigarrow u 上有多少个点 v 满足 \text{dk}_v=\text{hsh}。这个可以考虑从 1 到 n 扫描 i，依次维护 v\in[1,i] 的情况，则每次新扫到一个位置，需要修改（+1）的值拍平成 \text{dfn} 序后形如一段区间。

至于询问，对于 x\rightsquigarrow \text{lca}(x,y) 那条链上的贡献，考虑匹配的起点在哪个位置，容易发现链上的一个点 u 能够匹配当前询问串当且仅当 \text{dep}_u-\text{dep}_{\text{lca}(x,y)}\ge \text{len}，且 \text{uk}_u=\text{hsh}。因为这样才能包含在直链内。进一步发现满足这个条件的点位于 x\rightsquigarrow \text{anc}(\text{dep}_x-\text{len}-\text{dep}_{\text{lca}(x,y)},x) 上，那么拿 \text{num}_{0,x} 和 \text{num}_{0,\text{anc}(\text{dep}_x-\text{len}-\text{dep}_{\text{lca}(x,y)},x)} 差分即可。\text{lca}(x,y)\rightsquigarrow y 的查询方式类似，注意此时匹配的方向是自上而下，用 \text{num}_1 值差分计算。

此时，一共有 \mathcal{O}(n\sqrt{n}) 次修改，\mathcal{O}(n) 次查询，维护以 \text{dfn} 序为下标的差分数组，那么只需要分块支持 \mathcal{O}(1) 单点修改，\mathcal{O}(\sqrt{n}) 前缀查询即可。

值得注意的是，为了将同种哈希值的询问一起做，考虑使用排序将它们排在一个连续的区间内时，需要使用基数排序确保排序复杂度线性，才能保证 \boldsymbol{\mathcal{O}(\sqrt{n})} 次排序的总复杂度为 \boldsymbol{\mathcal{O}(n\sqrt{n})}。

\bf {Case\space 2}：跨过直链的情况

考虑分别处理每种串 s_k 的询问。

假设跨过直链的匹配发生在 u\rightsquigarrow v 上，其中 u,v 是 x\rightsquigarrow y 上的节点且 u 在 v 前。此时一定满足，\text{str}(u,\text{lca}(x,y)) 是 s_k 的前缀，\text{str}(\text{lca}(x,y),v) 是 s_k 的后缀。

同时，\text{str}(u,\text{lca}(x,y)) 是 \text{str}(x,\text{lca}(x,y)) 的后缀，\text{str}(\text{lca}(x,y),v) 是 \text{str}(\text{lca}(x,y),y) 的前缀。

考虑找到最长的长度 P,Q，使得 \text{str}(x,\text{lca}(x,y)) 存在长度为 P 的后缀为 s_k 的前缀；\text{str}(\text{lca}(x,y),y) 存在长度为 Q 的前缀为 s_k 的后缀。

考虑一个基础问题：

给出字符串 a,b，找到 b 的最长前缀使得它是 a 的后缀。求出这个最长长度。

解决方法是：找到 a 的一个后缀 a[i,|a|] 使得 |\text{lcp}(a[i,|a|],b)| 最大。记 L=|\text{lcp}(a[i,|a|],b)|，则 a[i,|a|] 最长的长度不超过 L 的 \text{border} 的长度即为所求。

接下来证明正确性。

\bf {Proof\space 2}

首先，这个 \text{border} 一定是同时是 b 的前缀和 a 的后缀。因为它是 a[i,|a|] 的前缀又是它的 \text{border}，说明 a[i,|a|] 存在这个 \text{border} 作为后缀。自然 a 也存在这个 \text{border} 作为后缀。记这里求出来的长度为 \text{len}。

考虑是否存在更长的答案。假设存在更长的答案长度为 \text{tmp}，其一定不超过 L，不然 a[i,|a|] 就不是使得 \text{lcp} 长度更大的后缀了。此时，a[i,|a|] 与 b 存在长度为 \text{tmp} 的 \text{lcp}。这时候 a[i,|a|] 开头的 \text{tmp} 个字符形成的字符串与结尾的 \text{tmp} 个字符形成的字符串相等。此时 \text{tmp} 是 a[i,|a|] 的一个更长的、长度不超过 L 的 \text{border}，矛盾。

因此不存在更长的答案，\text{len} 即为所求。

证毕。

将原问题转化成上述形式，那么 P 就是 \text{str}(\text{lca}(x,y),x) 最长的前缀长度满足它是 s_k^R 的后缀。这个和原问题显然是等价的，因为两个询问串都是原问题询问串的反串。不妨令新问题答案为 w，则反过来后原串对应的位置也相等，原问题的答案至少为 w；若原问题存在更长的答案 z，则反串中这些对应的位置也相等，z 就是新问题的一个更长的答案，与 w 的定义矛盾。

因此，P 就是在这个基础问题中 b=\text{str}(\text{lca}(x,y),x),a=s_k^R 的情况；Q 就是在这个基础问题中 b=\text{str}(\text{lca}(x,y),y),a=s_k 的情况。

先对 s_k 以及 s_k^R 进行后缀排序。

最长的长度不超过 L 的 \text{border} 很好求，由于要求的是某个后缀的 \text{border}，在其反串上就变成了前缀的 \text{border}，这两个问题也是等价的，和上面的证明类似。

因此，对于 s_k 和 s_k^R 建立失配树 T_k 和 T_k^R，并进行轻重链剖分。找到满足条件的后缀后，先看一下它的反串对应的是哪一棵失配树，然后在失配树上一条一条重链向上跳。失配树的根链是单调递减的（从节点到根）。若链顶大于 L，就整条链跳过，否则在链上二分，单次询问时间复杂度为 \mathcal{O}(\log n)。

接着考虑如何找到使得 L 最大的后缀。这个后缀一定满足，它要么是 a 中最大的字典序大小不超过 b 的后缀，要么是 a 中最小的字典序大小个超过 b 的后缀。换句话说，设这两个后缀与 b 的 \text{lcp} 长度分别为 A,B，则 L=\max\{A,B\}。

接下来给出证明：

\bf{Proof\space 3}

设它们的排名分别为 i,j。则一定有 j=i+1。因为根据定义，排名为 i+1 的后缀字典序大小已经超过了 b，但是排名在 [1,i]\cap\mathbb{Z} 内的后缀字典序大小都不超过 b。

考虑反证，假设排名为 \text{rnk}(\text{rnk}\ne i\land \text{rnk}\ne i+1) 的后缀会得到更大的 \text{lcp} 长度。

记这个更大的 \text{lcp} 长度为 \text{len}。分两种情况讨论：

  • 若 \text{rnk}\in[1,i)\cap\mathbb{Z}，则排名为 \text{rnk} 的后缀的前 \text{len} 位均与 b 的前 A 位相同。根据 \text{len} 的定义可知其第 A+1 位也与 b 的这一位相同。根据定义，排名为 i 的后缀的第 A+1 位小于 b 的这一位，或者说这一位不存在（空字符）。此时，排名为 i,\text{rk} 的两个后缀前 A 位相同都等于 b 的前 A 位。且后者的第 A+1 位大于前者的这一位。说明后者比前者字典序大，这与 \text{rnk}\in[1,i)\cap\mathbb{Z} 矛盾。

  • 若 \text{rnk}\in(i+1,|a|]\cap \mathbb{Z}，与上一种情况类似推导得到字典序大小上的矛盾即可证明。

证毕。

于是考虑求得排名 i。由于经过后缀排序，即这些后缀的字典序递增，所以答案有单调性，直接二分这个排名即可。

考虑如何求一条链上的字符串和序列上的字符串的最长公共前缀长度。对原树进行轻重链剖分，将边权转化为深度较深的端点的点权，则这条链会被表示成 \mathcal{O}(\log n) 条连续的重链区间。对于 \text{dfn} 序列形成的字符串维护哈希，对 s_k 和 s_k^R 也维护哈希。

一条一条重链匹配，若能全部匹配上，就算上这些长度，否则二分第一个不同的位置。只有第一条不匹配的重链需要二分，因此时间复杂度为 \mathcal{O}(\log n)。

这部分细节比较多，尤其是一方匹配完的边界情况，具体看代码中的 qlcp 部分。

此时，这个过程已经求出了 \text{lcp} 长度，顺带比较一下大小配合套在外面的二分。

那么 P,Q 均被我们求出来了。

求出来之后，我们只需要考虑 x\rightsquigarrow \text{lca}(x,y) 的后 P 个位置为开头处形成的匹配，因为不能匹配 s_k 更长的前缀了。

记这 P 个位置依次为 u_1\sim u_P，满足它们按照 \text{lca}(x,y)\rightsquigarrow x 路径上的顺序排列；记后 Q 个位置依次为 v_1\sim v_Q，满足它们按照 \text{lca}(x,y)\rightsquigarrow y 路径上的顺序排列。

则 u_i 为开头处能形成合法的匹配，当且仅当一下三点同时满足：

证明：

\bf{Proof \space 4}

  • 充分性：

    因为 i\ne |s_k|，所以跨过了 \text{lca}(x,y)。因为 s_k[1,P] 存在长度为 i 的 \text{border}，根据 P 的定义可以得到 \text{str}(u_i,\text{lca}(x,y))=s_k[P-i+1,P]=s_k[1,i]；因为 s_k^R[1,Q] 存在长度为 |s_k|-i 的 \text{border}，类似地，\text{str}(v_{|s_k|-i},\text{lca}(x,y))=s_k^R[1,|s_k|-i]，根据反串的定义得到 \text{str}(\text{lca}(x,y),v_{|s_k|-1})=s_k[i+1,|s_k|]。两者拼接恰好是 s_k。

  • 必要性：

    若 u_i 开头处可以形成合法的匹配，首先一定有 i\ne |s_k|，因为要跨过 \text{lca}(x,y)。其次 \text{str}(u_i,\text{lca}(x,y))=s_k[1,i]，根据 P 的定义，\text{str}(u_i,\text{lca}(x,y))=s_k[P-i+1,P]，因此 s_k[1,i]=s_k[P-i+1,P]，即 s_k[1,P] 存在长度为 i 的 \text{border}；类似地，\text{str}(v_{|s_k|-i},\text{lca}(x,y))=s_k^R[1,|s_k|-i]=s_k^R[Q-|s_k|+i+1,Q]，因此 s_k^R[1,Q] 存在长度为 |s_k|-i 的 \text{border}。

证毕。

所以，我们要统计有多少 i 合法，就是要统计有多少 i 满足这三个条件。

转化成失配树上的限制，就是要求有多少 i 满足 i 在 T_k 中 P 的根链上，且 |s_k|-i 在 T^R_k 中 Q 的根链上。

考虑离线 + 扫描线。对于所有 s_k 的询问，将它挂在 T_k 的 P 节点上。考虑深度优先搜索 T_k，在过程中一并维护数组 a_0\sim a_{|s_k|}。其中 a_j 表示有多少 i，满足：

则只要在 P 处单点查 a_Q 即可。

每次新扫到一个点 u，则和上一层深搜相比根链上增加了一个点 u 的贡献。考虑 |s_k|-u 的贡献，此时首先满足 u\ne |s_k|，发现只有它子树内的点的根链经过它，即只要这些点的 a_j 值要增加 u 的贡献。拍平成 \text{dfn} 序后将 a 映射过去，再进行差分，则需要支持的操作形如区间加、单点查，由于此处修改、询问同阶，树状数组维护即可。每次结束一个点的深搜时，删去它的贡献。

这部分就做完了，时间复杂度为 \mathcal{O}\left(n\log^2 n\right)。

综上，这个做法时空复杂度均为 \mathcal{O}(n\sqrt{n})，可以接受。前面也说过空间可以做到线性，只是需要一些精湛的卡常技艺。

AC Link & Code

码量 12.5 KB。

总结一下，本题考察了一下几方面的知识：

题目思路巧妙、性质极多、码量极大，对于选手的思维能力和代码能力都是一种不小的挑战，算是一道不可多得的字符串神仙 & 毒瘤题目。

完结撒花！