## 「雅礼集训 2017 Day1」字符串

机房没法编辑hexo。。。先丢这吧 ## 「雅礼集训 2017 Day1」字符串 题意：定义 $ f(S,T) $ 为 $ T $ 在 $ S $ 中的出现次数。 给串 $ S $ , $ m $ 个区间 $ [l_i,r_i] $ 和长度 $ k $ ,你要回答 $ Q $ 个询问，每次询问给一个长度为 $ k $ 的串 $ T $ 和上下界 $ a,b $ ,求 $$ \sum_{i=a}^bf(S,T[l_i,r_i]) $$ $ n,m,k,Q\le 10^5,kQ\le 10^5 $ 先讲两句闲话：之前听说过这是个清新的根号分治题，但一直不会做，暑假练了半个月SAM回来看这题，终于会了Orz。 解： 首先，如果对每个询问都暴力扫 $ m $ 个区间计算答案，那么复杂度不低于 $ \Omega(Qm) $ ,好像没有机会。 但是先别放弃，我们把具体的做法弄出来。统计串 $ T[l,r] $ 在串 $ S $ 中的出现次数是一个经典问题:让 $ T[1,r] $ 在SAM上跑匹配，找到对应节点（可能要舍弃某个前缀），并倍增找到parent树上最浅的祖先满足其长度至少为 $ r-l+1 $ .有 $ m $ 个区间，就令每个 $ r $ 维护一个`std::vector` ，对`vector`里面的每个元素都倍增求一下就好了。 所以复杂度是 $ \mathcal O(Qm\log n) $ 。不妨记为算法1. 注意 $ kQ\le 10^5 $ 的条件：当 $ k>\sqrt {10^5},Q<\sqrt {10^5} $ .这时候这个算法是可行的。因此考虑根号分治。 那 $ k\le \sqrt{10^5} $ 时怎么做呢？我们大力枚举 $ T $ 的每个子串 $ T[i,j] $ ，顺便在SAM上统计其出现次数 $ x $ .（注意这里不用像上面那样倍增，因为 $ T[i,j] $ 就是比 $ T[i,j-1] $ 多匹配了一个字符，暴力过去就好了）记有 $ y $ 个区间满足 $ l=i,r=j $ ,那么这个子串的贡献就是 $ xy $ . 统计 $ y $ 当然不能暴力。考虑把询问 $ (T,a,b) $ 拆成 $ (T,1,b)-(T,1,a-1) $ ，类似扫描线那样做就行。 复杂度 $ \mathcal O(Qk^2) $ .记为算法2. 小结一下，当 $ k>\sqrt {10^5} $ ，用算法1，否则用算法2.注意算法1多个log，因此可以在 $ k>700 $ (或500)时再用算法1，否则用算法2. [code link](https://loj.ac/submission/927031)