#P18747. [正睿NOI2021训练] 字符串
[正睿NOI2021训练] 字符串
字符串
给定长度为 的小写英文字母字符串 ,记从位置 开始的后缀为 。再给定长度为 的正整数序列 。
有 次询问,每次给出 ,求满足下列条件的有序对 的数量:
$$l\le i,j\le r,\qquad \operatorname{lcp}(S_i,S_j)\ge a_i.$$表示两个字符串的最长公共前缀长度。允许 。条件中的阈值是 ,因此交换 后不一定仍合法;若 ,以 为第一项的所有数对都不合法。
输入格式
第一行两个正整数 。
第二行字符串 ;第三行 个正整数 。
接下来 行,每行两个整数 。
输出格式
每次询问输出一行一个整数,表示合法有序对数量。
数据范围
,,。答案需要 64 位整数。
样例 1
输入
5 4
aabaa
1 2 1 2 1
1 3
2 4
3 5
1 5
输出
4
3
4
12