T1. P5840
算法:ACAM+BIT+树链剖分
自然地,我们会对 \(s_i\) 建 ACAM,然后建出一颗 fail 树。
此时我们考虑集合内加入一个新的字符串。每一个匹配到的点我们都会给从这个点一直到 fail 数的根节点上的的每一个点 \(+1\),但是每一个点只会加一遍。然后对于这棵树上的一个节点,他对最后答案的贡献即为他的子树内所有节点的和。显然的,复杂度会超标。
我们发现其实可以用树上差分来来维护这两个操作。由于一个点的子树的 dfs 序是连续的,所以对于第一种操作,我们在链的开始位置即为叶子结点 \(+1\),在链的终止位置的父亲 \(-1\) 即可。对于操作二,其实就是查询一个连续段的和。此时我们可以用 BIT 来维护。
接下来我们考虑一个链最后会加到那一个点。
由于我们碰到已经标记过得点,我们不会重复加。我们现对于所有需要加的点根据 dfs 需大小来排个顺序,所以终点就是这个点和上一个需要加的点的 lca 的儿子。这样这道题目就做完了。
标签:一个点,String,ACAM,dfs,我们,Record,fail,节点 From: https://www.cnblogs.com/Carousel/p/18207239