子串查询（二维前缀数组） 2018"百度之星"程序设计大赛 子串查询
Time Limit: 3500/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 835 Accepted Submission(s): 409
Problem Description
度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串
Input
第一行包含一个整数 n。
Output
对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第 ] 中字典序最小的子串个数，行末不要有多余空格。
Sample Input
1
2 3
AB
1 1
1 2
2 2
Sample Output
Case #1:
1
1
1
题意在给定区间内找最小的字典序的个数，一个字符的时候是最短的，只要计算最小的那个字符出现的次数，用二维前缀数组记录，参考自其他大佬
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[100005][30]; 4 int main() 5 { 6 int t; 7 scanf("%d",&t); 8 string s; 9 int cnt=1; 10 while(t--) 11 { 12 memset(a,0,sizeof(a)); 13 int n,q; 14 scanf("%d %d",&n,&q); 15 cin>>s; 16 a[0][s[0]-'A']=1; 17 printf("Case #%d: ",cnt++); 18 for(int i=1; i<s.size(); i++) 19 { 20 for(int j=0;j<26;j++) 21 a[i][j]=a[i-1][j];//二维前缀数组 22 23 a[i][s[i]-'A']++; 24 } 25 while(q--) 26 { 27 int x,y; 28 scanf("%d %d",&x,&y); 29 x--; 30 y--; 31 for(int i=0; i<26; i++) 32 { 33 if(x!=0&&a[y][i]-a[x-1][i]!=0){//左边界不是第一个的情况 34 printf("%d ",a[y][i]-a[x-1][i]); 35 break; 36 } 37 else 38 if(x==0&&a[y][i]!=0){//从第一个开始 39 printf("%d ",a[y][i]); 40 break; 41 } 42 } 43 } 44 } 45 return 0; 46 }