2479 「九省联考 2018」制胡窜

对于一个字符串 $S$，我们定义 $|S|$ 表示 $S$ 的长度。 接着，我们定义 $S_i$ 表示 $S$ 中第 $i$ 个字符，$S_{L,R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。特别的，如果 $L > R$ ，或者 $L < [1, |S|]$, 或者 $R < [1, |S|]$ 我们可以认为 $S_{L,R}$ 为空串。 给定一个长度为 $n$ 的仅由数字构成的字符串 $S$，现在有 $q$ 次询问，第 $k$ 次询问会给出 $S$ 的一个字符串 $S_{l,r}$ ，请你求出有多少对 $(i, j)$，满足 $1 \le i < j \le n$，$i + 1 \lt j$，且 $S_{l,r}$ 出现在 $S_{1,i}$ 中或 $S_{i+1, j−1}$ 中或 $S_{j,n}$ 中。

测试点	n	q	其它约定
$1$	$=50$	$=100$	无
$2 \sim 3$	$=300$	$=300$	无
$4 \sim 5$	$=2000$	$=3000$	无
$6 \sim 9$	$=100000$	$=100000$	$\sum \lvert S_{l,r} \rvert \le 10^6$
$10 \sim 12$	$=30000$	$=50000$	无
$13$	$=100000$	$=100000$	$S$ 中只有 $0$
$14 \sim 20$	$=100000$	$=300000$	无

对于所有测试数据，$1 \le n \le 10^5$，$1 \le q \le 3 · 10^5$，$1 \le l \le r \le n$。