#P6556. 美好的每一天
美好的每一天
美好的每一天
题目描述
回归天空是一件庄重的事情,所以卓司决定让大家分批次进行,给每个人给了一个小写字母 a 到 z作为编号
一个区间的人如果满足他们的编号重排之后可以成为一个回文串,则他们可以一起回归天空,即这个区间可以回归天空
由于卓司是一个喜欢妄想的人,他妄想了 个区间,每次他想知道每个区间中有多少个子区间可以回归天空
因为世界末日要来了,所以卓司的信徒很多
每次查询一个闭区间 ,统计其中所有满足 的非空连续子区间 。只要求每个被统计子区间的字符可以重新排列成回文,不要求原顺序本身就是回文;不同端点的子区间分别计数。
输入格式
从标准输入读入,第一行两个整数 。
接下来一行一个长为 的小写字母字符串,代表每个人的编号。
接下来 行,每行两个整数 ,代表询问区间,满足 。
输出格式
向标准输出输出 行,每行一个整数表示对应询问的答案。
样例 #1
样例输入 #1
6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1
样例输出 #1
16
4
2
2
3
1
样例 #2
样例输入 #2
6 6
aaabbb
1 2
2 3
3 4
4 5
5 6
1 6
样例输出 #2
3
3
2
3
3
17
样例 #3
样例输入 #3
4 1
yuno
1 4
样例输出 #3
4
提示
对于 的数据,。