【洛谷4770】 [NOI2018]你的名字（SAM，线段树合并）

传送门

Solution

做过的比较玄学的后缀自动机。
果然就像(Tham)所讲，后缀自动机这种东西考场考了不可能做的出来的。。。
考虑如果(l=1,r=|S|)的怎么做？
直接建后缀自动机然后跳。
接着就是(l,r)随机。。。
详细说明可点开蓝色题解按钮然后膜拜第一篇题解！
考虑线段树合并，我们关心的其实只有父亲关系和len对吧。
那么维护一下区域有多少个值，然后每一次查询符不符合要求就好了。

代码实现

代码戳这里