这题怎么才 \(\color{red}*2600\) 啊,我觉得有 $\color{maroon} *3000+ $,太菜了 /ll。
明天期中考试了,来一个官方题解做法涨涨 rp,复杂度稍劣还要离线,被爆了 /ll。题解区大佬说哈希狗都不写。
给出一棵 \(n\) 个点的树,边上有字母。\(q\) 次询问,每次给出一条路径 \(u\rightsquigarrow v\) 和一个字符串 \(s_i\),询问 \(s_i\) 在 \(u\rightsquigarrow v\) 的路径边上字母顺次拼接构成的字符串中出现了几次。
\(n,q\le 10^5\),记 \(S=\max\limits_{i=1}^q|s_i|\),\(\color{red}\boldsymbol{S\le 100}\)。
看到这题,我的第一反应是 CF1608G Alphabetic Tree,两题难度虽然差的有点多,做法的相似之处也不是很大,但是都是十分恐怖的重工业题。
进入正题,我们发现询问串的长度很小,考虑分别处理每一种长度的询问,记当前正在处理的长度为 \(len\)。
先对树进行重链剖分、边转点,则路径由 \(\mathcal{O}(\log n)\) 条重链组成。对于每一个询问,可以将字符串的出现位置分为完全在重链内以及跨越重链两类。
- 对于完全在重链内的位置:
先处理出每条重链自上而下以及自下而上的前缀哈希值,这样就可以求出重链内任意一条子路径、任意一种方向的哈希值。
求出每个点向上走 \(len\) 条边,向上、向下的哈希值 \(vu_i,vd_i\),并将它们离散化。对于每一种离散化值维护一个
std::vector
按顺序从小到大存放哈希值离散化后为该值的点的 \(dfn\)。则跳链的时候,设当前的链底的点为 \(x\),则问题可以变成:
查询在区间 \([dfn_{top_x}+len-1,dfn_x]\) 内,有多少点的权值为给定的值。
类似 P5838 一样,在
std::vector
上二分得到左右端点求区间长度即可。若当前重链在 \(u\rightsquigarrow \text{LCA}\) 的链上,则查询向上的哈希值,否则查询向下的哈希值。
- 对于跨越重链的位置:
在处理“完全在重链内的位置”时,用
std::vector
存下每一条重链的顶部、\(dfn\) 区间和方向。枚举起始的重链,则出现位置一定是起始重链长度为 \(len\) 的后缀(若不足则全部选,下同),以及该重链结尾位置再往后走 \(len\) 条边构成的字符串中(不然出现的起始位置要么没有跨越重链,要么不在起始重链内)。
暴力找出这条路径并记录其构成的字符串,进行哈希 / KMP 与询问串进行匹配。注意要保证跨越重链及起始位置在起始重链内。
做法大概就这样,好像也不是 too hard。接下来算复杂度。
输入以及重链剖分的预处理部分时间复杂度为 \(\mathcal{O}(n+qS)\)。
对于枚举 \(len\),预处理每个点向上 / 向下的哈希值并离散化的部分,一个点计算一次时间复杂度为 \(\mathcal{O}(\log n)\),要排序的元素一共有 \(\mathcal{O}(nS+q)\) 个,总时间复杂度是 \(\mathcal{O}((nS+q)\log (n+q))\)。
对于一个询问,处理“完全在重链内”的位置的时间复杂度为 \(\mathcal{O}(\log^2 n)\);处理“跨越重链的位置”时,枚举重链的时间复杂度为 \(\mathcal{O}(\log n)\),找出路径以及字符串匹配的时间复杂度为 \(\mathcal{O}(S)\)。所以一次询问的时间复杂度为 \(\mathcal{O}(\log n(\log n+S))\),总时间复杂度是 \(\mathcal{O}(q\log n(\log n +S))\)。
综上,该算法的时间复杂度为 \(\mathcal{O}((nS+q)\log (n+q)+q\log n(\log n+S))\)。配合 \(6\text{ s}\)
空间复杂度显然为 \(\mathcal{O}(n+qS)\)。
至此这题基本上解决了。完结撒花!
提交记录(含 \(\boldsymbol{8.9\,\text{KB}}\) 抽象代码)
标签:log,challenge,Moonwalk,len,哈希,mathcal,CF1045J,重链,复杂度 From: https://www.cnblogs.com/MnZnOIerLzy/p/17813543.html