#P6556. 美好的每一天

    ID: 6040 传统题 3000ms 384MiB 尝试: 4 已通过: 2 难度: 6 上传者: 标签>难度分类提高构造与建模奇偶性分析位运算异或前缀和离线与分治普通莫队奇偶块排序排序与序列处理离散化二分查找模拟与实现技巧预计算转移CF2100

美好的每一天

美好的每一天

题目描述

回归天空是一件庄重的事情,所以卓司决定让大家分批次进行,给每个人给了一个小写字母 a 到 z作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串,则他们可以一起回归天空,即这个区间可以回归天空

由于卓司是一个喜欢妄想的人,他妄想了 mm 个区间,每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了,所以卓司的信徒很多

每次查询一个闭区间 [l,r][l,r],统计其中所有满足 l≤L≤R≤rl\leq L\leq R\leq r 的非空连续子区间 [L,R][L,R]。只要求每个被统计子区间的字符可以重新排列成回文,不要求原顺序本身就是回文;不同端点的子区间分别计数。

输入格式

从标准输入读入,第一行两个整数 n,mn,m。

接下来一行一个长为 nn 的小写字母字符串,代表每个人的编号。

接下来 mm 行,每行两个整数 l,rl,r,代表询问区间,满足 1≤l≤r≤n1\leq l\leq r\leq n。

输出格式

向标准输出输出 mm 行,每行一个整数表示对应询问的答案。

样例 #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

提示

对于 100%100\% 的数据,n,m≤60000n,m\leq60000。