Luogu6292 区间本质不同子串个数

发表于 分类于 ， ， 阅读次数：

题意：给出字符串 ，每次询问 的本质不同子串个数。

，，时限 。

序列扫描线，逐渐增大右端点 ，并维护左端点 对应的询问 的答案。

考虑一个子串 能向询问 贡献的充要条件，不难想到选取最靠右的完整出现。具体地，右端点为 时， 中最后一次完整出现开头在 ，则需要满足 才能贡献。

维护一个数组 表示最后一次出现起点在 的串的个数。 的后缀和就是答案。

当 右移一位，会产生一个新的 endpos，这会更新从后缀点到根的路径，即所有后缀。这相当于先撤销所有后缀原来的贡献，再给 加一。

难点在于撤销贡献。对于一个 SAM 节点，将其“颜色”记为它最后出现的结束位置。对于某个节点，它的 是一段区间，结束位置一定，它对 （关注起始点）的影响也就是一段区间。

进一步地，parent tree 上一段相同颜色的点，其长度也是连续的，也只影响 的一个区间。它们可以用区间加法批量处理。

该过程非常像 LCT 的 access，于是在修改过程中，这样的段的个数均摊 。

当然，没必要真的写一个 LCT 来维护，有如下更初等的方法来模拟 access。

对于每种“颜色”，其在树上的出现位置形成一条链，起始点是叶节点，我们记录下终止点即最浅点。

若颜色编号递增，把颜色编号写在链起始的叶节点上，子树求 即可得知某个点当前的颜色。

每次断开某条链时，取用最浅点即可得到链顶，然后（由于断开了）把最浅点调整一下。

总复杂度 。