• Codeforces, The history of some recurring problem
• Luogu P6292 区间本质不同子串个数
• https://uoj.ac/problem/608
• https://www.fzoi.top/problem/4449

初见杀，实际套路，应该放一起做！

首先能离线当然考虑离线（Ukkonen 可以魔改支持左删，但是好像还是不能很好的支持左加和右删，否则我们甚至能莫队？），
那么我们只要维护一个线段树记录询问左端点在不同位置的答案，考察增加操作对线段树的影响，发现只影响 fail 树向上的节点，最后一步动态树优化即可，复杂度 O(nlog2n + mlogn)。

和 BZOJ_2555 相比，这里由于我们不需要强制在线，动态树不需要在后缀自动机插入字符时候跟随 SAM 变化形态，只需要在全部插入完后根据 fail 树构建即可，因而也可以树链剖分啊启发式合并啊替代动态树的环节。

具体来看，先考察 Luogu P6292 区间本质不同子串个数，每次添加新字符时，先把所有位置都加 1，然后类似 dquery 一题的搞法，我们记录上次添加的时刻以去掉重复计数的部分，而这只需要沿着 fail 树向上，并记录每个状态上次计数的时刻即可。这里的线段树只需要支持区间加减，区间求和，因而也可以用树状树组替代。

观察这里的动态树这里其实唯一的用处就只有压缩 fail 树 = =，我们只需要维护上次访问的标记即可，其它信息都可以从 SAM 中拿到，因为 Splay 之后父节点和自己刚好形成压缩后的 endpos 区间。

fzoi 那枚只需要把线段树从区间加常数变成加等差数列。再看 uoj 608，这里我们线段树需要支持的是区间等差数列 checkMax，由于这个标记是单调的，所以可以简单标记持久化，动态树同样只起到压缩 fail 树的功能，完全不用改！

Posted by xiaodao
Category: 日常