区间本质不同子串个数

题目描述

给定一个长度为 \(n\) 的字符串 \(S\)，\(m\) 次询问由 \(S\) 的第 \(L\) 到第 \(R\) 个字符组成的字符串包含多少个本质不同的子串。

定义两个字符串 \(a,b\) 相同当且仅当 \(|a|=|b|\) 并且对于 \(i\in[1,|a|]\) 都有 \(a_i=b_i\)。

输入格式

第一行一个长度为 \(n\) 的字符串 \(S\)。

第二行一个整数 \(m\)，表示询问次数。

接下来 \(m\) 行，第 \(i\) 行包含两个整数 \(l_i,r_i\)，描述第 \(i\) 次询问。

输出格式

\(m\) 行，每行一个整数，表示第 \(i\) 次询问的答案。

题解

看到这种离线且动态不太好做的区间信息可以想到扫描线，对于一个串，它会在最大的endpos值改变的时候将贡献的位置向后移动。
考虑加入一个字符后移动的串有哪些，在SAM上即为link树上当前点到根的所有子串。
于是我们需要维护SAM的link树，支持链修改。
用树剖是可做的，但是LCT做有非常好的性质，即一个splay中的串一定是同时改变的。
于是LCT维护一下，在开棵线段树维护一下答案（区间加等差数列）。