[集训队作业2018] 后缀树节点数
题目背景
来源:陈江伦 2018 候选队论文题
题目描述
给定一个长度为 $n$ 的字符串 $P$,有 $m$ 次询问,每次给定两个参数 $l$ , $r$,询问子串 $P[l,r]$ 所构成的后缀树的结点数。
如果你不了解后缀树,你也可以理解为对 $[l,r]$ 的反串建后缀自动机。
注意在本题中,后缀树的根节点不计入答案。
输入输出格式
输入格式
本题中用数字来表示字符串,不同的数字代表不同的字符,相同的数字代表相同的字符,数字的范围在 $[0,n]$ 之间。
第一行两个正整数 $n$ 和 $m$,表示字符串长度和询问个数。
第二行 $n$ 个用空格隔开的非负整数,表示这个字符串。
接下来 $m$ 行,每行两个正整数 $l,r$,表示询问子串 $[l,r]$ 的后缀树的结点数。
输出格式
输出 $m$ 行,每行一个正整数表示答案。
输入输出样例
输入样例 #1
7 2
2 1 3 1 3 1 4
1 7
4 5
输出样例 #1
10
2
说明
对于 $30\%$ 的数据:$n,m\le 3\times 10^3$;
对于 $100\%$ 的数据满足:$n\le 10^5$,$m\le 3\times 10^5$,字符串的每个数字 $\le n$。