UOJ Logo Universal Online Judge

UOJ

统计

在战前,蛐蛐国利用蛐口优势,发展了很多的劳动密集型产业。但经过了连年战乱后,蛐蛐国蛐口锐减,导致工业成本大大增加,国力低迷。为此,蛐蛐国必须推进产业升级,但缺乏相应的关键技术成为了一个症结。

伏特决定用跳蚤国的高新技术——机器蚤来解决这个难题。机器蚤是一种智能化机械,可以代替跳蚤和蛐蛐进行生产工作。但操作机器蚤是一个非常复杂的工作。具体来说,每只机器蚤都有独一无二的编号——一个非空小写字符串,如果一只机器蚤 $a$ 的编号 $s_a$ 是另一只机器蚤 $b$ 的编号 $s_b$ 的子串(连续子序列),那么 $b$ 就可以被 $a$ 控制。

一组机器蚤 $a_1,a_2,\ldots,a_k$ 是一个互不相同的机器蚤序列,使得对 $\forall 1\leq i < k$,$a_i$ 可以控制 $a_{i+1}$。对于一组这样的机器蚤,只需要一只蛐蛐操作 $a_1$,就可以同时控制里面所有机器蚤了。因此,给定若干机器蚤,将它们划分为最少数目的组就成为一个至关重要的问题。

现在伏特有一个机器蚤的命名串——一个非空小写字符串 $S$,伏特会询问你 $q$ 次,其中第 $i$ 次形如:考虑一个子串 $S[l_i,r_i]$ ,有一群机器蚤,它们的编号是这个子串的所有本质不同非空子串,那么最少能把它们划分成多少组?

输入格式

第一行两个正整数 $n,q$,分别表示 $S$ 的长度和询问次数。

接下来一行一个长度为 $n$ 的小写字符串 $S$。

接下来 $q$ 行,第 $i$ 行两个正整数 $l_i,r_i$,表示一个询问 $S[l_i,r_i]$ 。下标从 $1$ 开始。

输出格式

输出共 $q$ 行,第 $i$ 行一个正整数表示第 $i$ 次询问的答案。

样例一

input

4 1
abaa
1 4

output

3

explanation

询问 $S[1,4]=S$ ,因此所有机器蚤的编号是所有 $S$ 的非空子串,即 $a,b,aa,ab,ba,aba,baa,abaa$ 。

可以证明,最少能划分为 $3$ 个组,下面是其中一组合法方案(用编号指代机器蚤):

第 $1$ 组: $a,aa,abaa$

第 $2$ 组: $b,ab,aba$

第 $3$ 组: $ba,baa$

样例二

input

5 5
abbab
1 2
1 3
4 5
2 5
2 4

output

2
2
2
3
2

样例三

见附加文件中 ex_partition3.inex_partition3.out

样例四

见附加文件中 ex_partition4.inex_partition4.out

数据范围

对于所有数据, $1\leq n,q\leq 10^5,1\leq l_i\leq r_i \leq n$。

子任务编号 $n,q\leq$ 特殊性质 分值
$1$ $10$ $9$
$2$ $100$ $18$
$3$ $1000$ $21$
$4$ $25000$ $17$
$5$ $10^5$ 保证数据随机,其中字符串的每一位在字符集中等概率独立选取,每个询问在所有区间中等概率独立选取 $15$
$6$ $20$

时间限制:$4\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载