UOJ Logo Universal Online Judge

UOJ

#1089. 【ULR #4】A Nice Derangement of Epitaphs

附件下载 统计

给出长度为 $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}$