Problem A、小花梨的字符串
Description
小花梨有一个长度为𝑛且只包含小写字母的字符串。现在对其进行𝑞次询问。 每次询问字符串的一段区间[𝑙, 𝑟]，从[𝑙, 𝑟]区间内的所有子串中最多可以选出多少个字符串， 使得选出来的这些字符串存在一种排列方式满足相邻的两个字符串𝑎, 𝑏的最长公共后缀长度 大于等于𝑚𝑖𝑛(𝑠𝑡𝑟𝑙𝑒𝑛(𝑎), 𝑠𝑡𝑟𝑙𝑒𝑛(𝑏)) − 1。
Input
第一行输入两个正整数𝑛和𝑞，分别表示字符串长度和询问次数。 第二行为长度为𝑛的字符串。接下来𝑞行，每行两个正整数𝑙, 𝑟表示询问的区间。 (1 ≤ 𝑛 ≤ 10000,1 ≤ 𝑞 ≤ 10000,1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛)
Output
输出𝑞行，第𝑖行输出第𝑖次询问的答案
Example
Sample Input
3 3 abc
1 1
1 2
1 3
Sample Output
Note： [1,1]内有1个子串：𝑎 ，存在排列𝑎满足要求，长度为1 [1,2]内有3个子串：𝑎, 𝑏, 𝑎𝑏，存在排列𝑎, 𝑎𝑏, 𝑏满足要求，长度为3 [1,3]内有6个子串：𝑎, 𝑏, 𝑐, 𝑎𝑏, 𝑏𝑐, 𝑎𝑏𝑐，存在排列𝑎𝑏, 𝑏, 𝑐, 𝑏𝑐, 𝑎𝑏𝑐, 𝑎满足要求，长度为6
这个题意很拗口，所以梳理一下大致细节：
这个题意乍一看着像是压轴级别Last word的，但是，观察一下它的样例输入的第三次询问的解释：
a,𝑎𝑏, 𝑏, 𝑐, 𝑏𝑐, 𝑎𝑏𝑐.
好像没什么规律，但是把它们稍微一改变排列顺序：
a,ab,b,abc,bc,c
每一对相邻字符串的公共子序列的长度都至少为1，完全符合要求。但是最主要的重点是：这代表着每次取它的前缀，然后每次切除前缀的一个前缀，直至剩下一个字符（或者说取前缀的后缀）。
简单地说，就是对于字符串abc，它有三种前缀a,ab,abc。a只有一个字符，无法切除前缀,ab有一个非本身前缀a,切除一次得到b，接着处理abc，分别切除a,b，然后把这些切除后产生的字符串都排列一下就是符合题意的答案。
那么这个问题的关键就变成了求出询问区间内字符串的前缀的个数与每个前缀异于本身的后缀的个数，前者就是字符串长度本身，后者就是一个单纯的等差数列关系，总和的话利用公式求和即可。