[Exercises on 2022.5.11] 字符串转风车煮饭吃蒸饭吃脂肪层

例 1. \(\text{CF504E Misha and LCP on Tree}\)

首先可以想到预处理从根到每个点和每个点到根的哈希值（需要处理向上和向下的两种情况），然后进行二分，用长链剖分 \(\mathcal O(1)\) 找祖先即可做到 \(\mathcal O((n+m)\cdot \log n)\)。或者对整棵树重链剖分，维护 \(\rm dfs\) 序列上的哈希值（当然之前的方法也可行），这样路径会被划分成 \(\mathcal O(\log n)\) 条重链，对两条路径进行扫描，一直到不同的重链再进行二分，两个 $\log $ 是分开的，总共是 \(\mathcal O(m\log n)\)。后面的做法如果觉得求哈希不保险的话可以换成 \(\rm sam\)，只需要将每条重链向上向下两种情况扔进 \(\rm sam\) 即可。

例 2. \(\text{CF204E Little Elephant and Strings}\)

一些闲话：我字符串真的好垃圾啊！猛然发现自己只有字符串模板题水平 o(TヘTo)。

考虑 \(\rm SA\)。将所有字符串接在一起，中间的字符必须两两不同，然后做一个 \(\rm SA\)。固定左端点 \(l\)，向右延伸找到恰好使得 排名 在 \([l,r]\) 之中的后缀所属字符串种类为 \(k\) 的 \(r\)。容易发现，这样的 \(r\) 是递增的，所以可以维护一个双指针。对于每个尺取到的 \([l,r]\)，我们找到排名在 \([l,r]\) 之间的后缀的 \(\rm lcp\)，这就说明 \(\rm lcp\) 及其所有前缀都是满足题意的子串。

现在的问题是我们如何将满足题意的子串贡献到每个字符串上，还是考虑 \([l,r]\) 是一段区间比较好维护，所以可以将贡献累加在后缀上（因为我们是取 \(\rm max\)，所以不存在算重的问题，令这个数组为 \(f\)），用个随便什么东西维护区间取 \(\max\)，单点查值都行。最后将后缀上的贡献累加到字符串上即可。

完了吗？

事实上，上文的算法并不完全正确。还是考虑尺取到的 \([l,r]\)，我们只保证这是 "以每个 \(l\) 开始，恰好使得 排名 在 \([l,r]\) 之中的后缀所属字符串种类为 \(k\)"，我们不继续向右拓展基于一个贪心 —— 再向右 \(l\) 的答案只会更劣。但这同时也意味着某些排名 \(>r\) 的后缀没有被贡献。事实上，解决方案很简单：

同时，我们也可以发现根本不需要维护区间取 \(\max\)，只用更新 \(f_i\) 即可！

另外，向左拓展一定是不优的，这个很容易证明。再另外 \(k=1\) 的情况有些特殊，需要另行考虑。

例 3. \(\text{CF914F Substrings in a String}\)

前几天模拟赛出了一道很像的题目，当时用 \(\rm bitset\) 卡了半天的常……这题 \(\rm bitset\) 的解法就不再赘述。

首先可以发现，这题如果没有修改、\(l,r\) 的限制就是经典 \(\rm sam\) 问题：在 \(\rm trie\) 树上跑询问串 \(y\)，查询跑到节点的子树 \(\rm size\) 和。

最近做了很多知道 \(\sum\) 取值转化成根号算法的题，对于这题可以考虑一个朴素的思路 —— 重构 \(\rm sam\)。

显然我们是做一个属于区间 \([l,r]\) 的字符的自动机重构，复杂度与 \(r-l\) 是线性相关的。考虑把序列分成 \(n/B\) 块，那么

• 若 \(|y|> B\)。容易发现满足此条件的 \(y\) 个数不超过 \(n/B\)，所以直接重构区间 \([l,r]\) 的自动机再查询即可，复杂度 \(\mathcal O(n^2/B)\)；
• 若 \(|y|\le B\)。对每块维护一个自动机，最初对每个块都打上一个 \(\rm tag\) 表示需要重构。那么在操作 \(1\) 时就会至多重构一个块。对于单次询问，查询整块与边角块后还要注意查询两个块之间产生的贡献。复杂度 \(\mathcal O(n^2/B+nB)\).

话是这么说，但这题也挺卡常的??，这里放一份代码吧：\(\text{My Submission.}\)