子串查询

度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！

为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串 A[1,n]=a1a2⋯anA[1,n]=a1a2⋯an，接下来他会向你提出 qq 个问题 (l,r)(l,r)，你需要回答字符串 A[l,r]=alal+1⋯arA[l,r]=alal+1⋯ar 内有多少个非空子串是 A[l,r]A[l,r] 的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列，两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。

记 |S||S| 为字符串 SS 的长度，对于两个字符串 SS 和 TT，定义 SS 的字典序比 TT 小，当且仅当存在非负整数 k(≤min(|S|,|T|))k(≤min(|S|,|T|)) 使得 SS 的前 kk 个字符与 TT 的前 kk个字符对应相同，并且要么满足 |S|=k|S|=k 且 |T|>k|T|>k，要么满足 k<min(|S|,|T|)k<min(|S|,|T|) 且 SS 的第 k+1k+1 个字符比 TT 的第 k+1k+1 个字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。

Input

第一行包含一个整数 TT，表示有 TT 组测试数据。

接下来依次描述 TT 组测试数据。对于每组测试数据：

第一行包含两个整数 nn 和 qq，表示字符串的长度以及询问的次数。

第二行包含一个长为 nn 的只包含大写英文字母的字符串 A[1,n]A[1,n]。

接下来 qq 行，每行包含两个整数 li,rili,ri，表示第 ii 次询问的参数。

保证 1≤T≤101≤T≤10，1≤n,q≤1051≤n,q≤105，1≤li≤ri≤n1≤li≤ri≤n。

Output

对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第 xx 组测试数据，接下来 qq行，每行包含一个整数，表示字符串 A[l,r]A[l,r] 中字典序最小的子串个数，行末不要有多余空格。

Sample Input

12 3AB1 11 22 2

Sample Output

Case #1:111

这是一道考察前缀和的题，但是却有点儿怪，要不怎么说是百度之星资格赛上的题呢，题目说了一大堆，其实题意就是找区间中最小字母出现的次数，那么由前缀和的思想，我们需要知道在区间左端点位置上最小字母出现的次数以及在区间右端点位置上最小字母出现的次数（通过一次循环就能得到），两边相减就得到结果了。

但是怎么查询最小字母呢？难道要遍历区间之间所有的字母吗？显然这是不可取的，因为题目给出的区间范围以及查询范围是1e5，1e5 * 1e5 = 1e10,这肯定会超时的，因此我们定义一个二维数组，在第一维度上是26个英文字母，第二维度是字符串长度，其值为这个字母在当前位置出现的次数。我们只需要循环26个字母就可以了，如果这个字母在区间左端点之前出现的次数和区间右端点出现的次数相同，那么说明这个字母没有在区间内出现过，遍历字母从0（代表 'A'）开始，当找到一个字母在区间左端点之前出现的次数和区间右端点出现的次数相同不相同时，那么这个字母一定是最小的，次数输出结果并跳出循环。

#include<iostream>#include<cstring>using namespace std; int vec[26][100010];char s[100010];int main(){ int k; cin>>k; int cut=1; while(k--){ memset(vec,0,sizeof(vec)); memset(s,0,sizeof(s)); int n; int q; cin>>n>>q; scanf("%s",s+1); for(int i=1;i<=n;i++){ vec[s[i]-'A'][i]++; } for(int i=0;i<=25;i++){//记录在 j 位置 'i' 这个字母出现的次数，其中i表示A~Z个大写字母 for(int j=1;j<=n+1;j++){ vec[i][j]+=vec[i][j-1]; } } printf("Case #%d:\n",cut++); while(q--){ int left; int right; scanf("%d%d",&left,&right); for(int i=0;i<=25;i++){ //如果说i字母在left位置之前出现的次数和在right位置之前出现的次数相同， //说明在区间lert~right上没有i字母 if(vec[i][right]!=vec[i][left-1]){ printf("%d\n",vec[i][right]-vec[i][left-1]); break;//因为i依次增大，所以如果找到那就是最小的，所以跳出循环进行下一组数据测试。 } } } } return 0;}