【日常小测】String

题目大意

先给定一个长度为$n(n \le 50000)$的字符串$S$
之后给定$m(m \le 50000)$个操作(强制在线)，操作分两种

1. 在字符串$S$末尾加入一个字符
2. 将$S$的子串$[l,r]$取出来，设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

解题报告

我们考虑用一棵线段树来支持插入斜率为$-1$的线段，并询问区间最值
这个是用来维护答案的，至于为什么插入的是线段，待会儿再说
至于具体实现，因为斜率相同，所以我们只需要将直线的纵截距插入即可，换言之我们只需要支持区间取$\max$即可

现在假设我们已经在维护了$[1,r-1]$的答案，并且我们在维护$[1,r]$回答所有右端点为$r$的询问
考虑插入第$r$个字符会影响哪些部分的答案：显然只会影响$fail$链上的答案
我们记录$last_x$表示$SAM$上的结点x代表的串在$S$中出现的最后一次的时间
我们注意到一条$fail$链上$last_x$一定是相等的，所以我们只需要考虑最长长度$l$
于是我们需要在线段树的$[last_x-l+1,last_x]$区间插入$x+y-(last_x+1)=0$的直线
之后我们更新$fail$链上的$last_x$，至于询问我们只需要到线段树上查询区间最值
当然维护$fail$树的话，我们需要使用$LCT$。

注意到$LCT$的一个$splay$里的$last_x$相等，所以单次$access$只会贡献$\log n$次区间取$\max$操作
所以我们已经能在$O(n \log ^2 n)$的时间复杂度内解决离线版本了
现在考虑在线版本，我们将线段树可持久化即可