题意

https://uoj.ac/problem/608
给定一个字符串 T，每次询问一个子串 T[l,r]，返回其最长重复子串的长度。

做法

证明？参考 官方题解。
我们来讨论怎么用 SAM 搞子串的重复子串。

首先回忆怎么用 SAM 求最长重复子串。
直接返回 fail 树上非叶子节点的 len[u] 就好。

再考虑怎么求某个前缀 T[1,r] 的最长重复子串。
我们考虑离线，按照 r 端点从小到大排序，
按照顺序每次在 fail 树上找到前缀所对应的叶子节点，
往根节点染色即可。用染色路径上第一个碰到的节点的 len 的长度更新答案。
因为每个节点只会被染色一次，所以暴力染色即可。

最后考虑一般情况 T[l,r]，我们显然需要对染色进行区分，
我们希望每个状态越晚被染色越好，因为越晚，它可能对答案的贡献就越长。
我们不妨画一下示意图。。考虑下面的情况。。考虑到时刻 r 的时候经过节点 u。
u 历史上在时点 l1 和 l2 都被染色过，且 len[u] = 4，那么有：
设 l1 < l2 < r。
—l1, —l2, —r
那么我们可以忽略 l1，并且只有在 l <= l2-3 的時候，才能得到
完整的 4 长度的贡献，在 l2 时刻，因为询问的左区间不够长，只有对答案带来 1 的贡献。

具体说来，不妨对每个可能三元组 (l,r,u)。
r 表示当前染色的时点，l 表示历史上这个节点最晚被染色的时点。
u 表示 l, r 到根路径上的某个公共祖先。

我们可以用线段树。。。
支持询问区间最值，
以及区间覆盖，和区间等差数列覆盖两个操作即可。

具体说来就是。。。
checkMax1(1, l-len[u], len[u])，表示对区间 [1, 1-len[u]] 与 len[u] 取 max。
以及
checkMax2(l-len[u]+1, l)，表示对 l-len[u]+1, l-len[u]+2，…, l 这个区间分别 checkMax 上 l, l-1, …, 1 这个递减数列。

因为染色过程总是叶子到根节点的路径，所以可以用动态树。
这里的动态树也可以用启发式合并替代。