给出长度为 $n$ 的字符串 $s$。
有 $q$ 次询问,每次给出 $l, r$,求 $s_{l\cdots r}$ 的不相交相等子串对数,即 $\sum_{l\le a\le b < c\le d\le r} [s_{a\cdots b} =s_{c\cdots d}]$。
输入格式
第一行整数 $n,q$,第二行字符串 $s$。
随后 $q$ 行每行一对整数 $l, r$,表示一次询问。
输出格式
对于每次询问,输出一个数表示答案。
样例 1
input
5 5
aabab
1 2
3 4
1 5
2 5
3 5
output
1
0
5
3
1
样例 2
input
12 10
aababababbaa
1 12
2 7
2 3
11 12
9 12
5 9
4 7
2 8
1 5
7 10
output
47
10
0
1
2
6
3
16
5
3
数据范围
本题采用捆绑测试。
对于所有数据,保证 $1\le n,q\le 10^5$,字符串仅包含小写字母。
| 子任务编号 | 特殊性质 | 分数 |
|---|---|---|
| $1$ | $n, q \le 10^3$ | $10$ |
| $2$ | $l=1$ | $30$ |
| $3$ | 字符串随机生成,且仅包含 ab |
$20$ |
| $4$ | $n,q\le 3\times 10^4$ | $20$ |
| $5$ | 无 | $20$ |
时间限制:$\texttt{10s}$
空间限制:$\texttt{2GB}$

鄂公网安备 42010202000505 号