• https://codeforces.com/blog/entry/62331
• https://www.luogu.com.cn/problem/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 树向上，并记录每个状态上次参与计数时的位置即可。这里的线段树只需要区间加减，区间求和，因而也可以树状树组。动态树只需要维护上次访问的标记，以及这组被压缩的 endpos

再看 uoj 608，

Posted by xiaodao
Category: 日常